1.取上中位数

题目：

          给定两个有序数组arr1和arr2，两个数组长度都为N，求两个数组中所有数的上中位数。要求：时间复杂度O(logN)。

     例如：

         arr1 = {1,2,3,4};

         arr2 = {3,4,5,6};

         一共8个数则上中位数是第4个数，所以返回3。

         arr1 = {0,1,2};

         arr2 = {3,4,5};

         一共6个数则上中位数是第3个数，所以返回2。

思路：

     (1)假设两个数组长度为偶数，取中间节点index=1            1  2  3  4            1‘ 2’ 3‘ 4’         若2 == 2‘ ，则直接返回；         若2 > 2', 说明 2 至少排第4， 所以3,4可以排除，1’ 2‘（2’ 最多排第3）可以排除，所以对剩下的1 2和3‘ 4’ 递归         若2 < 2‘，同理递归1’ 2‘和3、4.

 

(2)假设两个数组长度为奇数，取中间节点index=2.          1  2  3  4  5          1‘ 2’ 3‘ 4’ 5’         若3 == 3‘ ，则直接返回；         若3 > 3', 说明 3 至少排第6， 所以4,5可以排除，1’ 2‘（2’ 最多排第4）可以排除，所以对剩下的1 2 3和 3‘ 4’  5‘递归，其实3也能排除，但是为了保证两个数组的长度一样，保留3         若3 < 3‘，同理递归1’ 2‘ 3’和3、4 、5.

代码：

int getUpMedian(const vector
    
      & arr1, int start1, int end1,const vector
     
       & arr2, int start2, int end2) {              if(start1 == end1)                return min(arr1[start1], arr2[start2]);            int size = end1-start1+1;            int halfSize;              if(size&1 == 1)//奇                halfSize = (size + 1)/2;            else//偶                halfSize = size/2;                      if(arr1[start1+halfSize - 1] == arr2[start2 + halfSize - 1])                return arr1[start1 + halfSize - 1];            else if(arr1[start1 + halfSize - 1] > arr2[start2 + halfSize - 1])                return getUpMedian(arr1,start1,start1+halfSize-1,arr2,end2-(halfSize-1),end2);            else                return getUpMedian(arr1,end1-(halfSize-1),end1,arr2,start2,start2+halfSize -1);}int getUpMedian(vector
      
        arr1, vector
       
         arr2) {//主函数          if(arr1.size() != arr2.size())            return -1;        if(arr1.size() == 0)            return -1;        return getUpMedian1(arr1,0,arr1.size()-1,arr2,0,arr1.size() -1 );}
       
      
     
    

2.取不等长有序数组的最小K个数

题目：

       给定两个有序数组arr1和arr2，在给定一个整数k，返回两个数组的所有数中第K小的数。要求：如果arr1的长度为N，arr2的长度为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；

思路：

     分三种情况考虑，假设arr1的长度N小于等于arr2的长度M

     (1)若K<=N 

             结果为 arr1[0---K-1]和arr2[0---K-1]取中位数

     (2)若 N<K<=M。先将arr2分为[0--K-N-1],[K-N-----K-1],[K,M-1]三部分

             当arr2[K-N-1]>=arr1[N-1]，结果为arr2[K-N-1]

             否则，arr2[0--K-N-1]部分的所有数据一定至多在K-1位置(极端情况下，arr1[N]占据K位置)。而arr2[K,M-1]区间段的元素至少在K+1位置。因此结果对长度为N的两段区间段arr1[0,N-1]和arr2[K-N,K-1]取中位数即可。

     (3)若K>M>N。先将划分arr1[0,K-M-1][K-M,N-1]两段区间，arr2[0,K-N-1][K-N,M-1]

            当arr2[K-N-1]>=arr1[N-1]，结果为arr2[K-N-1]

            当arr1[K-M-1]>=arr2[M-1]，结果为arr1[K-M-1]

            两者不满足的话。则如前所叙述，arr1[0,K-M-1]和arr2[0,K-N-1]的元素都在位置K之前，至多为K-1。因此结果为长度为M+N-K的两段区间arr1[K-M,N-1]和arr2[K-N,M-1]的中位数。

     时间复杂度最大为情况(2)，即为所要求。

代码：

int findKthNum(vector
    
      arr1, vector
     
       arr2, int kth)        {            int size1 = arr1.size();            int size2 = arr2.size();             if(size1 > size2)                return findKthNum(arr2, arr1, kth);//ensur           if(kth <= size1)                return getUpMedian(arr1, 0, kth - 1, arr2, 0, kth - 1);//前k个，取中位数即可           else if (kth <= size2 && kth > size1)           {                if(arr2[kth - size1 - 1] >= arr1[size1 - 1] )                    return arr2[kth - size1 - 1];				else                   return getUpMedian(arr1, 0, size1-1, arr2, kth-size1, kth-1);           }           else            {                if(arr2[kth-size1-1] >= arr1[size1-1])                    return arr2[kth-size1-1];                if(arr1[kth-size2-1] >= arr2[size2-1])                    return arr1[kth-size2-1];               return getUpMedian(arr1, kth-size2, size1-1, arr2, kth-size1, size2-1);           } }
     
    

参考：

   1.