leetcode:4.寻找两个有序数组的中位数

柔光的暖阳◎ 2022-03-10 13:25 196阅读 0赞

### 题目描述： ###

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

##### 示例： #####

示例1：

nums1 = [1, 3]
    nums2 = [2]
    
    则中位数是 2.0

示例2：

nums1 = [1, 2]
    nums2 = [3, 4]
    
    则中位数是 (2 + 3)/2 = 2.5

##### 题目难度：困难 #####

##### 分析： #####

题目比较好理解，如果只看最后结果的话，很容易想到把两个数组合并，并且排序后就可以轻松的找到中位数，但这样不符合题目的意思，因为要求的时间复杂度为 O ( l o g ( m + n ) ) O(log(m + n)) O(log(m\+n))。这样一来不管你怎么合并排序都不可能达到题目要求，最好的也是 O ( n l o g n ) O(nlogn) O(nlogn)这个级别。代码如下：

class Solution { 
        public double findMedianSortedArrays(int[] nums1, int[] nums2) { 
        	// 定义一个大的数组用来存放两个小数组
            int[] nums3 = new int[nums1.length + nums2.length];
            // 分别把两个数组放在nums3里面
            for (int i = 0; i < nums1.length; i++) { 
                nums3[i] = nums1[i];
            }
            for (int i = nums1.length, j = 0; i < nums3.length; i++, j++) { 
                nums3[i] = nums2[j];
            }
            // 对数组排序
            Arrays.sort(nums3);
            // 对有序数组来说，只要根据数组的长度就可以轻松找到中位数。
            return nums3.length % 2 == 0 ?
                    (nums3[nums3.length / 2 - 1] + nums3[nums3.length / 2]) / 2.0 :                                     nums3[nums3.length / 2];
        }
    }

##### 小结： #####

时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，这里为了省事，直接调用了API，虽不合法要求，但是结果是对的，执行速度较慢。

##### 扩展： #####

根据题目的意思，是两个已经排好序的数组了，如果要合并的话，其实可以用二路归并排序，虽然时间复杂度也是 O ( n l o g n ) O(nlogn) O(nlogn)，但是前面的步骤都省略了，只需要最后的一个合并步骤即可，所以速度会快跟多，目前排名第一的代码如下（搬运）：

class Solution { 
        public double findMedianSortedArrays(int[] nums1, int[] nums2) { 
    		int nums2length = nums2.length;
    		// 定义一个大的数组用来存放两个小数组
    		int[] r = new int[nums1.length + nums2length];
    		int index = 0;
    		int j = 0;
    		/* 双层for循环，只要内层的元素小于外层的元素就把内层的元素放入数组中， 这样一来肯定会把nums2中所有小的元素放在最前面，直到找到一个比nums1中的元素 更大的，再把他放入即可，重复操作，即可以nums1中的元素和nums2中部分元素排序放好。 */
    		for (int num : nums1) { 
    			while (j < nums2length && num > nums2[j]) { 
    				r[index] = nums2[j];
    				j++;
    				index++;
    			}
    			r[index] = num;
    			index++;
    		}
    		// 这一步是把nums2中剩下的元素依次放入，因为前一个步骤中可能会因为
    		//nums2.length > nums1.length。导致nums2会漏掉后面的部分元素。
    		for (; j < nums2length; j++) { 
    			r[index] = nums2[j];
    			index++;
    		}
    		// 最后一步就是在排好序的数组中找到中位数即可。
    		int mi = r.length / 2;
    		return r.length % 2 == 1 ? r[mi] : (r[mi - 1] + r[mi]) / 2.0;
    	}
    }

##### 小结： #####

此方法比较好理解，速度也快（不愧是排名第一的），巧妙的把两个排好序的数组放入一个大数组中，然后即可求出中位数。

##### 总结： #####

简单的算法和想法不一定是慢的，有时候往往有奇效。