当前位置:   article > 正文

【力扣刷题】二分查找:4. 寻找两个正序数组的中位数_找中位数算法时间复杂度

找中位数算法时间复杂度

题目:

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

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/median-of-two-sorted-arrays

解题思路:

题目难度主要是在时间复杂度上面,O(log(m+n)),我一开始是用的双指针来实现的,两个指针分别指向两个数组的初始位置,因为两个数组都是已知且有序的,则长度也已知,所以只需要找到中点位置(奇数个元素),或者是中点的两个元素除以2(偶数个元素),则使用双指针很方便,但是时间复杂度就不会满足了,为O(m+n),所以要达到题目要求的时间复杂度,得想另一种实现方式,二分法->二分查找。

因为数组是有序的,可以实现一半一半的排除,假如我们要找第k小的数字,我们比较两个数组的第k/2的位置的数字大小,如果其中一个更小,那么它和它前面的数字都不会是第k小的数字,则都可以排除。

例子:

数组A:1,3,4,9

数组B:1,2,3,4,5,6,7,8,9,10

过程:

因为n1 = 4,n2 = 10,所以要找的中点元素为第7个和第8个元素的和除以2。找第7小的元素过程如下:

①A中比k小的有k/2-1个,B中有k/2-1个,这时4>3,说明B中1,2,3(前k/2个元素)都可以排除

②已经排除了三个元素,在两个新数组中,只需要找剩下的元素的第4小的元素。则k=7-3=4,k/2=2,比较两个k/2处的元素,较小的那一处可以排除。这时5>3,则排除A的元素1,3

③又排除了A数组中的前面两个元素1,3,那么剩下的元素k=4-2=2,k/2=1,继续判断k/2处的元素,4==4,排除哪个都可以,去掉一个还是会保留一个元素的。

④那就排除下面的数组元素,然后又排除了一个元素,k=2-1=1,则比较两个数组的元素,较小的那个元素则所求。

⑤其实算法找第奇数还是第偶数个小的数字,不会影响算法的整体,只需要把传的参数改为k=8就可以了,在算法进行中,k 的值都有可能从奇数变为偶数,最终都会变为 1 。

⑥特殊情况,在排除元素的过程中,会遇到数组元素长度小于k/2的情况,那这种时候,只需要将指针的箭头指向该数组的末尾元素,再进行比较,如果小于,则直接排除,相当于找另一个数组里面剩余的k-length的元素即可。

代码:

  1. class Solution {
  2. public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  3. int n1 = nums1.length;
  4. int n2 = nums2.length;
  5. int left = (n1 + n2 + 1)/2;
  6. int right = (n1 + n2 + 2)/2;
  7. //将元素总数是奇数/偶数的情况统一,如果为奇数,就求两次一样的值的和除以2
  8. return (getK(nums1,nums2,left,0,n1-1,0,n2-1)+getK(nums1,nums2,right,0,n1-1,0,n2-1))/2;
  9. }
  10. public double getK(int[] nums1,int[] nums2,int k,int start1,int end1,int start2,int end2){
  11. int leng1 = end1 - start1 + 1;
  12. int leng2 = end2 - start2 + 1;
  13. //如果有元素数组为空了,那就直接从另外一个数组中寻找要求的值
  14. if(leng1 == 0) return nums2[start2 + k - 1];
  15. if(leng2 == 0) return nums1[start1 + k - 1];
  16. //k==1,那么就比较两个元素中较小的那个,返回小的元素
  17. if(k == 1) return Math.min(nums1[start1],nums2[start2]);
  18. //递归,每次比较剩余元素数组k/2处的元素,小的部分全部排除
  19. //要注意比较剩下的元素是否还有k/2个元素,没有的话直接将指针赋值到数组尾元素
  20. int i = start1 + Math.min(leng1,k/2) - 1;
  21. int j = start2 + Math.min(leng2,k/2) - 1;
  22. if(nums1[i] >= nums2[j]){
  23. return getK(nums1,nums2,k-(j-start2+1),start1,end1,j+1,end2);
  24. }else{
  25. return getK(nums1,nums2,k-(i-start1+1),i+1,end1,start2,end2);
  26. }
  27. }
  28. }

递归终止的条件就是某一个数组为空或者k==1的时候,则根据不同情况返回不同的值即可,元素总数个数为奇数的时候,则求两次(left和right值相同)一样的值相加除以2;为偶数就求left和right对应的值的和除以2,返回即可。

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/921103?site
推荐阅读
相关标签
  

闽ICP备14008679号