It is actually find Kth element in two sorted array


  • 0
    D

    '''

    int findKthElement(vector<int>::const_iterator begin_1, 
                       size_t len_1,
                       vector<int>::const_iterator begin_2, 
                       size_t len_2, 
                       size_t k) {
        if (len_1 > len_2) {
            return findKthElement(begin_2, len_2, begin_1, len_1, k);
        }
        if (len_1 == 0) {
            return *(begin_2 + k - 1);
        }
        if (k == 1) {
            return std::min(*begin_1, *begin_2);
        }
        auto dis_1 = std::min(k / 2, len_1);
        auto dis_2 = k - dis_1;
        if (*(begin_1 + dis_1 - 1) < *(begin_2 + dis_2 - 1)) {
            return findKthElement(begin_1 + dis_1, len_1 - dis_1, begin_2, len_2, k - dis_1);
        } else if (*(begin_1 + dis_1 - 1) > *(begin_2 + dis_2 - 1)) {
            return findKthElement(begin_1, len_1, begin_2 + dis_2, len_2 - dis_2, k - dis_2);
        } else {
            return *(begin_1 + dis_1 - 1);
        }
        return -1;
    }
    

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.