微软面试题： LeetCode 4. 寻找两个正序数组的中位数 hard 出现次数：3

题目描述：

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

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

方法1：

总体思路：同时遍历 num1 和nums2 ，比较num1和nums2中当前遍历到的两个元素 nums1[i] 和 nums[j] 的大小。若nums1[i] 小则

i 前进一位，j 不动，反之，j 前进一位，i 不动，直到遍历到中位数的下标或者其中一个数组遍历结束再继续单独遍历另一个数组，

直到找到中位数。由于中位数需要根据元素个数是奇数和偶数两种情况讨论，此种算法实现上细节判断较多，容易出错，最终写出的代码

结构也比较凌乱。且时间复杂度 O（m + n）,空间复杂度O（1）性能上也不符合题目的要求。

重点关注第二种 O(log (m+n)) 的算法

  1 #include <string>

  2 #include <vector>

  3 #include <cmath>

  4

  5 using namespace std;

  6 class Solution {

  7 public:

  8 //O(m+n)

  9     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)

 10     {

 11         int m = nums1.size();

 12         int n = nums2.size();

 13         bool odd = true;//奇数

 14         if( (m+n) % 2 == 0)    odd = false;//偶数

 15         int mid = (m+n)/2;

 16         int k = 0;

 17         int front = 0;

 18         int i = 0,j = 0;

 19         for(;i<m && j<n;)

 20         {

 21             if(k == mid)

 22             {

 23                 if(odd)

 24                 {

 25                     return nums1[i]<nums2[j]?nums1[i]:nums2[j]/1.000000;

 26                 }

 27                 else

 28                 {

 29                     int tmp = nums1[i]<nums2[j]?nums1[i]:nums2[j];

 30                     return (tmp+front)/2.000000;

 31                 }

 32             }

 33             else

 34             {

 35                 if(nums1[i]<nums2[j]){

 36                     front = nums1[i];

 37                     i++;

 38                 }

 39                 else

 40                 {

 41                     front = nums2[j];

 42                     j++;

 43                 }

 44                 k++;

 45             }

 46         }

 47       //  printf("k = %d mid = %d i = %d j = %d \n",k,mid,i,j);

 48         if(k == 0)

 49         {

 50             if(j == n)

 51             {

 52                 return odd?nums1[mid]/1.0:(nums1[mid]+nums1[mid-1])/2.0;

 53             }

 54             else if(i == m){

 55                 return odd?nums2[mid]/1.0:(nums2[mid]+nums2[mid-1])/2.0;

 56                 }

 57             else{

 58                 return 0.000000;

 59             }

 60         }

 61         if(odd)

 62         {

 63             int index ;

 64             if(j == n ) //j 已经走完 i 未走完

 65             {

 66                 index = i + (mid+1 - k)-1 ;

 67                 return index < m?nums1[index]/1.000000:0.000000;

 68                 // return nums1[index];

 69             }

 70             else

 71             {

 72                 index = j + (mid+1 - k)-1;

 73                 return index < n?nums2[index]/1.000000:0.000000;

 74                 // return nums2[index];

 75             }

 76         }

 77         else

 78         {

 79             if(j == n)

 80             {

 81                 int idx = i + (mid+1 - k) -1;

 82                 if(idx <= 0 )

 83                 {

 84                     return (nums2[n-1] + nums1[0])/2.000000;

 85                 }

 86                 else

 87                 {

 88                     int frt = max(nums1[idx-1],nums2[n-1]);

 89                     return (nums1[idx] + frt)/2.000000;

 90                 }

 91             }

 92             else

 93             {

 94                int idx = j + (mid+1 - k) -1;

 95                 if(idx <= 0 )

 96                 {

 97                     return (nums1[m-1] + nums2[0])/2.000000;

 98                 }

 99                 else

100                     {

101                         int frt = max(nums2[idx-1],nums1[m-1]);

102                         return (nums2[idx] + frt)/2.000000;

103                     }

104             }

105         }

106     }

107 };

方法2：转化为求第 k 小数的元素

分析：上面的解法中同时遍历两个数组中的元素并比较大小，对小的元素，在该数组中前进，并统计前进的步数，前进到 (n + m)/2 步，就遍历到

中位数。每次前进相当于去掉不可能是中位数的一个值，也就是一个个排除。由于数列是有序的，其实我们完全可以一半儿一半儿的排除。

具体思路可参考：https://leetcode.wang/leetCode-4-Median-of-Two-Sorted-Arrays.html

代码如下：

 1 class Solution {

 2 public:

 3     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)

 4     {

 5         int n = nums1.size();

 6         int m = nums2.size();

 7         int left = (n + m +1)/2;

 8         int right = (n + m +2)/2;

 9         //将n+m是奇数和偶数的情况合并，如果是奇数，会求两次两同的k,最终返回两个正序数组的一个中位数

10         //如果是偶数，最终返回两个正序数组的中间两个中位数的平均值

11         return (getKth(nums1,0,n-1,nums2,0,m-1,left)+getKth(nums1,0,n-1,nums2,0,m-1,right))*0.5;

12     }

13 /*

14 使用二分法

15 求 nums1[start1,end1]和 nums2[start2:end2]的第k小元素

16 */

17     double getKth(vector<int>& nums1, int start1,int end1,vector<int>& nums2,int start2,int end2,int k)

18     {

19         int len1 = end1 - start1 +1;

20         int len2 = end2 - start2 +1;

21         //始终将元素少的那个数组作为第一个参数，这样就能保证如果有数组空了，一定是第一个参数的数组

22         if(len1 > len2){

23            return getKth(nums2,start2,end2,nums1,start1,end1,k);

24         }

25         //递归出口1，nums1[start1,end1]空了，返回nums2[start2,end2]中的 第 k 个元素

26         if(len1 == 0)

27         {

28             return nums2[start2 + k - 1];

29         }

30         //递归出口2，返回两个数组的第 start 个元素中较小的一个

31         if(k == 1)

32         {

33             return min(nums1[start1+k-1],nums2[start2+k-1]);

34         }

35         //nums1[start1:end1] 中 第 k/2 个元素的下标，如果nums1[start1:end1] 长度小于 k/2，则取nums[start1:end1]最后一个元素下标

36         int i = start1 + min(k/2,len1) - 1;

37         //nums2[start2:end2] 中 第 k/2 个元素的下标,nums2[start2:end2] 长度一定不会小于 k/2

38         int j = start2 + k/2 - 1;

39         //int j = start2 + min(k/2,len2) - 1;

40         //递归地求 第 k、k/2、k/4、... 、1 个元素，直到遇到递归出口跳出

41         if(nums1[i] < nums2[j])

42         {

43             return getKth(nums1,i+1,end1,nums2,start2,end2,k - (i - start1 +1));

44         }

45         else

46         {

47             return getKth(nums1,start1,end1,nums2,j+1,end2,k - (j - start2 +1));

48         }

49     }

50 };

巴特西

微软面试题： LeetCode 4. 寻找两个正序数组的中位数 hard 出现次数：3

最新文章

热门文章