DMOZ中文网站分类目录-免费收录各类优秀网站的中文网站目录.
  • DmozDir.org
DMOZ目录快速登录入口-免费收录各类优秀网站的中文网站目录.由人工编辑,并提供网站分类目录检索及地区分类目录检索,是站长免费推广网站的有力平台!

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

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

  • 已被浏览: 24 次2020年11月21日    来源:  https://www.cnblogs.com/wangxf2019/p/14017680.html
  • 题目描述:给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗? 方法1:总体思路: 同时遍历

    题目描述:

      给定两个大小为 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 };
    View Code

     

    方法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 };

     


    以上信息来源于网络,如有侵权,请联系站长删除。

    TAG:中位数 序数 微软 面试题 次数

  • 上一篇:使用Actor模型管理Web Worker多线程
  • 与“微软面试题: LeetCode 4. 寻找两个正序数组的中位数 hard 出现次数:3”相关的资讯
  • 一文搞懂所有Java集合面试题
  • WPF有关控件和模板样式设计的微软官方文档
  • .NET5发布,这个微软“全家桶”会是.NET的春天吗?
  • 微软开源的 AI 工具,让旧照片焕发新生
  • JAVA面试题笔试题