LintCode 65. 两个排序数组的中位数

题目描述

两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。

样例：

输入:

A = [1,2,3,4,5,6]

B = [2,3,4,5]

输出:

3.5

样例：

输入:

A = [1,2,3]

B = [4,5]

输出:

3

思路

最直观的思路是就是将两个数组合并成一个数组，然后将这个数组进行排序，找到这个数组的中位数就可以。

相关代码

//这是最容易想到的思路，还可以使用其他排序方式，当然这种思路的算法复杂度为O(n^2)
void SelectSort(vector<int>&a, int n) {//选择排序
     int mix, temp;
     for (int i = 0; i<n - 1; i++){ //每次循环数组，找出最小的元素，放在前面，前面的即为排序好的
         mix = i; //假设最小元素的下标
         for (int j = i + 1; j<n; j++) //将上面假设的最小元素与数组比较，交换出最小的元素的下标
             if (a[j]<a[mix])
                mix = j;
        //若数组中真的有比假设的元素还小，就交换
         if (i != mix){
            temp = a[i];
            a[i] = a[mix];
            a[mix] = temp;
         }
    }
}

double findMedianSortedArrays(vector<int> &A, vector<int> &B){
       // write your code here
       int n = B.size();
       for (int i = 0; i < n; i++){
           A.push_back(B[i]);
       }

       int m = A.size();
       int left = 0, right = m;
       //选择排序
       SelectSort(A, m);
       double res;
       int mid = (left + right) / 2;
       if (m % 2 == 0){
          return res = (A[mid] + A[mid - 1]) / 2.0;
       }
       else{
          return A[mid];
       }
}
           

思路二

采用二分的思路来做。但是这道题难就难在要在两个未合并的有序数组之间使用二分法，这里我们需要定义一个函数来找到第K个元素，由于两个数组长度之和的奇偶不确定，因此需要分情况来讨论，对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。下面重点来看如何实现找到第K个元素，首先我们需要让数组1的长度小于或等于数组2的长度，那么我们只需判断如果数组1的长度大于数组2的长度的话，交换两个数组即可，然后我们要判断小的数组是否为空，为空的话，直接在另一个数组找第K个即可。还有一种情况是当K = 1时，表示我们要找第一个元素，只要比较两个数组的第一个元素，返回较小的那个即可。

相关代码

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
       int m = nums1.size(), n = nums2.size();
       int left = (m + n + 1) / 2, right = (m + n + 2) / 2;
       return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
 }
 
 int findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
     if (i >= nums1.size()) return nums2[j + k - 1];
     if (j >= nums2.size()) return nums1[i + k - 1];
     if (k == 1) return min(nums1[i], nums2[j]);
     int midVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX;
     int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;
     if (midVal1 < midVal2) {
        return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
     } 
     else {
        return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
     }
}
           

参考文档