算法——分治

分治

1. 两个有序数组的中位数

• 题目描述——Leetcode 4

  给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的 中位数 。

  算法的时间复杂度应该为O(log (m+n))。

• 解题思路

  将两个数组合并为一个正序数组来看。当m+n是偶数时，中位数为第$\frac{m+n}{2}$和第$\frac{m+n}{2}+1$个数的平均值；当m+n是奇数时，中位数为第$\frac{m+n}{2}+1$个数。因此可以设

  $k=\left\{\begin{array}{l}\frac{m+n}{2},\frac{m+n}{2}+1&,m+n为偶数 \\ \frac{m+n}{2}+1&,m+n为奇数\end{array}\right.$

  将问题转化为求解两个正序数组的第k小的值。

  设两个数组分别为A和B，将A[k/2-1]和B[k/2-1]进行比较。假设A[k/2-1]<B[k/2-1]则易得A[k/2-1]最多为第k-1小的元素(A[0...k/2-2]<A[k/2-1],B[0...k/2-2]<A[k/2-1])。此时可将A中下标为0~k/2-1的元素排除，同时k-k/2。

  设i和j分别为两个数组的有效起始下标，初始时都为0。k根据m+n的结果进行初始化。具体迭代过程如下：

  • $A[\frac{k}{2}-1+i]\leq B[\frac{k}{2}-1+j]$：排除$A[i]-A[\frac{k}{2}-1+i]$，$i += \frac{k}{2}$，$k = k-\frac{k}{2}$。
  • $A[\frac{k}{2}-1]>B[\frac{k}{2}-1]$：排除$B[j]-B[\frac{k}{2}-1+j]$，$j+=\frac{k}{2}$，$k = k-\frac{k}{2}$。

  特殊情况处理

  • 如果$k=1$且两个数组都有有效数字，则返回两个数组首元素的最小值。

  • 如果$\frac{k}{2}-1+i>m-1$或者$\frac{k}{2}-1+j>n-1$，则取相应数组中的最大值进行比较，此时$k$的更新根据实际排除的数的个数进行。

  • 如果数组有效数据为空，即全部被排除，则直接返回另一个数组中第$k$小的元素。

• 代码实现

  class Solution {
  public:
      double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
          int m = nums1.size(),n = nums2.size();
          int len = m+n;
          if(len%2 == 0)
              return (getMinK(nums1,nums2,len/2)+getMinK(nums1,nums2,len/2+1))/2;
          else
              return getMinK(nums1,nums2,len/2+1);
      }
      //获取两个数组第k小的元素
      double getMinK(vector<int>&nums1,vector<int>&nums2,int k){
          int i = 0,j = 0;	//数组起始下标
          int m = nums1.size(),n = nums2.size();
          int p = 0,q = 0;	//实际比较的两个数的下标
          while(i<m&&j<n&&k>1){
          	p = i+k/2-1<m ? i+k/2-1:m-1;
              q = j+k/2-1<n ? j+k/2-1:n-1;
              if(nums1[p]<=nums2[q]){
                  k = k-(p-i+1);
                  i = p+1;
              }else{
                  k = k-(q-j+1);
                  j = q+1;
              }
          }
          if(k == 1 && i<m && j<n)
              return nums1[i]<=nums2[j]?nums1[i]:nums2[j];
          while(i<m)
              return nums1[i+k-1];
          while(j<n)
              return nums2[j+k-1];
          return 0;
      }
  };

• 复杂度分析