면접 문제: 두 개의 질서 있 는 배열 의 모든 수 K 작은 수 를 찾 습 니 다.

4542 단어 데이터 구조
두 개의 질서 있 는 배열 arr 1 과 arr 2 를 정 하고 하나의 정수 k 를 정 하여 두 배열 의 모든 수 에서 k 작은 수 를 되 돌려 줍 니 다.요구: arr 1 의 길이 가 N 이 고 arr 2 의 길이 가 M 이 라면 시간 복잡 도 는 O (log (min {M, N}) 에 도달 하 십시오.
  :
arr1 = {1,2,3,4,5}
arr2 = {3,4,5}
k = 1;
  1        ,    1
arr1 = {1,2,3}
arr2 = {3,4,5,6}
k = 4
  3      4   ,    3
#include 
#include  
#include 
using namespace std;

int FindKthNum(int* arr1, int len1, int* arr2, int len2, int k)
{
    assert(k >= 0 && len1 + len2 >= k);

    if(len1 > len2)
    {
        return FindKthNum(arr2, len2, arr1, len1, k);
    }

    if(len1 == 0)
        return arr2[k-1];
    if(k == 1)
        return min(arr1[0], arr2[0]);                          

    int range1 = min(k/2, len1), range2 = k - range1;
    // arr1[0,range1) + arr2[0,range2)        k  
    // 1.arr1[range1-1] == arr2[range2-1],             k 
    // 2.arr1[range1-1] < arr2[range2-1],   arr1[0,range1)    
    // 3.arr1[range1-1] > arr2[range2-1],   arr2[0,range2)    

    if(arr1[range1-1] == arr2[range2-1])
        return min(arr1[range1-1], arr2[range2-1]);
    else if(arr1[range1-1] < arr2[range2-1])//  range1 
        return FindKthNum(arr1+range1, len1-range1, arr2, len2, k-range1);
    else
        return FindKthNum(arr1, len1, arr2+range2, len2-range2, k-range2);

}

void test()
{
    int a1[5] = {1,2,3,4,5};
    int a2[3] = {3,4,5};

    cout<5, a2, 3, 1)<int a11[3] = {1,2,3};
    int a22[4] = {3,4,5,6};
    vector<int> arr11(a11, a11+3);
    vector<int> arr22(a22, a22+4);
    cout<3, a22, 4, 4)<

좋은 웹페이지 즐겨찾기