查找两个有序数组中第K大的元素（C++实现）

// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from stdin).

#include <iostream>
#include <vector>
using namespace std;

// find the kth smallest num in two sorted array, k start from 1
int kth_small(vector<int> a, vector<int> b, int k) {
    assert(k>=1);
    vector<int>::iterator ai = a.begin();
    vector<int>::iterator bi = b.begin();
    int ret = 0;
    while(ai != a.end() && bi != b.end()) {
        if(k < 2) {
            ret = (*ai < *bi)?*ai:*bi;
            return ret;
        }
        if(*ai > *bi) {
            bi ++;
        } else if(*ai < *bi) {
            ai ++;
        } else {
            ai ++;
            bi ++;
        }
        k--;
    }
    return ret;
}

void print_vector(vector<int> vet) {
    for(vector<int>::iterator iter = vet.begin(); iter != vet.end(); iter++) {
        cout<<*iter<<" ";
    }
    cout<<endl;
}

int main() {
    // test data
    vector<int> alist;
    vector<int> blist;
    for(int i = 6; i < 100; i+=3) alist.push_back(i);
    for(int i = 2; i < 100; i+=2) blist.push_back(i);
    cout<<"alist: "<<endl;
    print_vector(alist);
    cout<<"blist: "<<endl;
    print_vector(blist);  
    cout<<"kth smallest: "<<endl;
    cout<<kth_small(alist, blist, 1)<<endl;
    
    return 0;
}

 

欢迎关注微信公众号——计算机视觉：