• LeetCode HOT 100 —— 4.寻找两个正序数组的中位数


    题目

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

    算法的时间复杂度应该为 O(log (m+n))
    在这里插入图片描述
    在这里插入图片描述

    思路

    正序数组,立即推—>二分查找

    如果本题不要求时间复杂度O(log(n + m )),可以考虑暴力解法,时间复杂度为O(n + m)

    方法一:暴力

    先将两个数组合并,两个有序数组的合并也是归并排序中的一部分,然后根据奇数还是偶数,返回中位数

    java代码如下:

    class Solution {
    	public int findMedianSortedArrays(int[] nums1,int[] nums2){
    		int[] nums;//创建一个新数组
    		int m = nums1.length;
    		int n = nums2.length;
    		nums = new int [m + n];//长度为两个数组之和
    		//若有一个数组为空,那么直接返回另一个数组的中位数
    		if(m == 0){//若nums1为空
    			if(n % 2 == 0){
    				return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
    			} else {
    				return nums2[n / 2];
    			}
    		}	
    		if(n == 0){//若nums2为空
    			if(m % 2 == 0){
    				return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
    			} else {
    				return nums1[m / 2];
    			}
    		}
    		//若两个数组均不为空,则加入到新数组
    		int count = 0;//新数组下标,记录新数组的长度
    		int i = 0, j = 0;
    		while(count != (m + n)){
    			if(i == m){//如果nums1已经遍历完了
    				while(j != n){
    					nums[count++] = nums2[j++];
    				}
    				break;//当两个数组都遍历完时,退出循环
    			}
    			if(j == n){
    				while(i != m){
    					nums[count++] = nums1[i++]; 
    				}
    				break;
    			}
    			
    			if(nums1[i] < nums2[j]){
    				nums[count++] = nums1[i++];
    			} else {
    				nums[count++] = nums2[j++];
    			}
    		}
    					
    		//求新数组的中位数
    		if(count % 2 == 0){
    			return ((nums[count / 2 - 1] + nums[count / 2 ]) / 2.0);
    		} else {
    			return nums[count / 2];
    		}
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    另一种思路是不用合并两个有序数组,只用找到中位数的位置即可,因为两个数组长度知道,那么合并之后的数组的中位数的下标位置也可以计算出来,然后用两个指针,分别指向两个数组,每次将较小值的指针后移一位,直到到达中位数位置,这种方法虽然空间复杂度降为了O(1),时间复杂度仍然是O(n + m)

    方法二:二分查找

    题目中的log的时间复杂度,只有用二分的方法才能达到

    根据中位数定义,当m + n是奇数时,中位数是两个有序数组中的第(m+n)/2个元素,当m+n是偶数时,中位数是两个有序数组中的第(m+n)/2个元素和(m+n)/2 +1个元素的平均值(注意,这里说的是第几个元素,下标是需要再 减一的),因此本题可以转化成寻找两个有序数组中的第 k 小的数,其中k为(m+n)/2或者(m+n)/2 + 1

    假设两个有序数组分别是 A 和 B。要找到第 k 个元素,可以比较 A[k/2−1]B[k/2−1],由于 A[k/2−1]B[k/2−1]的前面分别有 A[0 .. k/2−2]B[0 .. k/2−2],即 k/2−1个元素,对于 A[k/2−1]B[k/2−1] 中的较小值,最多只会有 (k/2−1)+(k/2−1)≤k−2个元素比它小,那么它就不能是第 k小的数了,所以可以将 A[k/2−1]B[k/2−1] 中的较小值也一起排除

    一共归纳出三种情况:

    • 如果 A[k/2−1],则比 A[k/2−1]小的数最多只有 A 的前 k/2−1个数和 B的前 k/2−1个数,即比 A[k/2−1]小的数最多只有 k−2个,因此 A[k/2−1]不可能是第 k 个数,A[0]A[k/2−1]也都不可能是第 k个数,可以全部排除;
    • 如果 A[k/2−1]>B[k/2−1],则可以排除 B[0]B[k/2−1]
    • 如果 A[k/2−1]=B[k/2−1],则可以归入第一种情况处理。

    可以看到,比较 A[k/2−1]B[k/2−1]之后,可以排除 k/2不可能是第 k 小的数,查找范围缩小了一半(比如排除了A[0]A[k/2−1],一共k/2个元素)。

    同时,在排除后的新数组上继续进行二分查找,并且根据我们排除数的个数,减少 k 的值,这是因为排除的数都不大于第 k 小的数。

    有以下三种情况需要特殊处理:

    • 如果 A[k/2−1]或者 B[k/2−1]越界,那么可以选取对应数组中的最后一个元素。在这种情况下,必须根据排除数的个数减少 k 的值,而不能直接将 k 减去 k/2;
    • 如果一个数组为空,说明该数组中的所有元素都被排除,可以直接返回另一个数组中第 k小的元素;
    • 如果 k=1,只要返回两个数组首元素的最小值即可。

    java代码如下:

    class Solution {
    	public double findMedianSortedArrays(int[] nums1,int[] nums2){
    		int m = nums1.length;
    		int n = nums2.length;
    		int totalLen = m + n;
    		if(totalLen % 2 == 1){
    			int midIdx = totalLen / 2;//这里是数组的中点下标
    			double median = getKThNumber(nums1,nums2,midIdx + 1);//这里参数是第k小的数,所以数组下标midIdx对应的就是第midIdx + 1小的数
    			return median;
    		} else {//如果数组长度是偶数
    			int midIdx1 = totalLen / 2 - 1;
    			int midIdx2 = totalLen / 2;//分别表示数组中点左右下标
    			double median = (getKThNumber(nums1,nums2,midIdx1 + 1) + getKThNumber(nums1,nums2,midIdx2 + 1)) / 2.0;
    			return median; 
    		}
    	}
    	
    	public int getKThNumber(int[] nums1,int[] nums2,int k){
    	
    		int m = nums1.length;
    		int n = nums2.length;
    		int idx1 = 0, idx2 = 0;
    		int kthNumber = 0;
    		
    		while(true){
    			//处理边界情况
    			if(idx1 == m){//如果数组为空,即长度为0,那么直接返回另一个数组第k小的元素
    				return nums2[idx2 + k -1];
    			}
    			if(idx2 == n){
    				return nums1[idx1 + k - 1];
    			}
    			if(k == 1){//则返回两个数组首元素的最小值即可
    				return Math.min(nums1[idx1],nums2[idx2]);
    			}
    			
    			//正常情况
    			int half = k / 2;//每次都能排除k/2个元素
    			int newIdx1 = Math.min(idx1 + half, m) - 1;
    			int newIdx2 = Math.min(idx2 + half, n) - 1;
    			int pivot1 = nums1[newIdx1], pivot2 = nums2[newIdx2];
    			//取二者最小者
    			if(pivot1 <= pivot2){
    				k -= (newIdx1 - idx1 + 1);//k减去排除的元素数量
    				idx1 = newIdx1 + 1;
    			} else {
    				k -= (newIdx2 - idx2 + 1);
    				idx2 = newIdx2 + 1;
    			}
    		}
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    时间复杂度:每进行一次循环,就减少 k/2 个元素,所以时间复杂度是 O(log(k),而 k=(m+n)/2,所以最终的复杂也就是 O(log(m+n)

  • 相关阅读:
    探索国密:C#中实现SM2、SM3、SM4算法的深度指南
    逍遥自在学C语言 | 变量、常量与数据类型
    据包捕获和分析工具作原理和用途
    八股文第六天
    LRU最近最少使用算法
    Qt::绘制框架-选择模式-selectedMode
    JS如何判断文字是否溢出(被ellipsis)?
    【Java 基础篇】Java Condition 接口详解
    Python基础知识入门(三)
    2022年最火的十大测试工具,你掌握了几个
  • 原文地址:https://blog.csdn.net/qq_39473176/article/details/127993554