1. 题目

  给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n)) ，可以假设 nums1 和 nums2 不会同时为空。

2. 思路

arr1[1, 2, 3, 4, 5]arr2[5, 6, 7, 8, 9, 10]

  arr1 元素个数为奇数，从中间 [3] 开始选择，将 [3] 进行分割为 [3, 3] ，令 Left1 = 3 ，Right1 = 3，arr2 元素个数为偶数，从 中间 [7, 8] 开始选择，令 Left2 = 7 ，Right2 = 8 ，因为 Left2 > Right1，所以需要重新选择，arr1 选择项向右移动一位增大，arr2 选择项向左移动一位减小，则arr1 再次选择 [4] ，将 [4] 进行分割为 [4, 4] ，令 Left1 = 4 ，Right1 = 4，arr2 重新选择 [6, 7]，令 Left2 = 6 ，Right2 = 7 ，判断 Left2 > Right1，需要按照该步骤重新选择，直到 arr1 的选择项为 [5]，arr2 的选择项为 [5, 6]，此时 Left1 = 5 ，Right1 = 5，Left2 = 5 ，Right2 = 6，因为 Left1 <= Right2，Left2 <= Right1，所以求得中位数为 (max(Left1+Left2) + min(Right1+Right2))/2。   考虑到数组奇偶不同，选择项不同，因此采用补位想法，通过补位将单个数组位数改变为奇数，两个数组的位数之和改变为偶数，即

Arr1[*, 1, *, 2, *, 3, *, 4, *, 5, *]Arr2[*, 5, *, 6, *, 7, *, 8, *, 9, *, 10, *]

  元素 3 在补位数组 Arr1 中为 Arr1[5]，所以计算 arr[(5-1)/2] = arr[2]，arr[5/2] = arr[2]，于是在原 arr1 选择为 [3, 3]，同理 * 在补位数组 Arr2 中为 Arr2[6]，所以计算arr[(6-1)/2] = arr[2]，arr[6/2] = arr[3]，于是在原 arr1 选择为 [7, 8]。通过此方法来进行奇偶数组元素的选择。

3. 程序

#include <iostream> #include <vector> #include <climits> #define max(x, y) (x>y? x: y) #define min(x, y) (x<y? x: y) using namespace std; double jp(vector<int>& vec1, vector<int>& vec2){ int ini1, ini2; int num1, num2; int Left1, Right1, Left2, Right2; num1 = vec1.size(); num2 = vec2.size(); if(num1>num2) return jp(vec2, vec1); ini1 = num1; ini2 = num2; while(ini1<=2*num1 && ini1>=0){ Left1 = (ini1==0? INT_MIN: vec1[(ini1-1)/2]); Right1 = (ini1==num1*2? INT_MAX: vec1[ini1/2]); Left2 = (ini2==0? INT_MIN: vec2[(ini2-1)/2]); Right2 = (ini2==num2*2? INT_MAX: vec2[ini2/2]); if(Left1>Right2){ ini1 = ini1 - 1; ini2 = ini2 + 1; } else if(Left2>Right1){ ini1 = ini1 + 1; ini2 = ini2 - 1; } else break; } return (max(Left1, Left2)+min(Right1, Right2))/2.0; } int main(){ double aver; vector<int> vec1 = {1, 5, 5, 6}; vector<int> vec2 {3, 5}; aver = jp(vec1, vec2); cout<<aver<<endl; return 0; }

4. 重点

(1) 两个数组元素个数分别为奇数和偶数；

(2) 两个数组元素个数为奇数；

(3) 两个数组元素个数为偶数；

(4) 通过补位获取每个数组分割左右的两个元素。