4. 寻找两个正序数组的中位数

1. 题目描述:

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

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

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2


示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5


示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000


示例 4:

输入:nums1 = [], nums2 = [1]
输出:1.00000


示例 5:

输入:nums1 = [2], nums2 = []
输出:2.00000

2. 解题思路

1. 使用归并的方式,合并两个有序数组,得到一个大的有序数组。大的有序数组的中间位置的元素,即为中位数。

2. 不需要合并两个有序数组,只要找到中位数的位置即可。由于两个数组的长度已知,因此中位数对应的两个数组的下标之和也是已知的。维护两个指针,初始时分别指向两个数组的下标 00 的位置,每次将指向较小值的指针后移一位(如果一个指针已经到达数组末尾,则只需要移动另一个数组的指针),直到到达中位数的位置。

2.1 C++

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
 4         int n1 = nums1.size(), n2 = nums2.size();
 5         vector<int> obj;
 6         double temp= 0.0;
 7         int i = 0, j = 0;
 8         while(i < n1 || j < n2){
 9             if(i != n1 && j != n2){
10                 if(nums1[i] <= nums2[j]){
11                     obj.push_back(nums1[i]);
12                     i++;
13                 }else{
14                     obj.push_back(nums2[j]);
15                     j++;
16                 }
17             }else if(i == n1){
18                 obj.push_back(nums2[j]);
19                 j++;
20             }else if(j == n2){
21                 obj.push_back(nums1[i]);
22                 i++;
23             }
24         }
25         int n = (n1 + n2) / 2;
26         if((n1 + n2) % 2 == 0){
27             temp = (obj[n - 1] + obj[n]) / 2.0;
28         }else{
29             temp = obj[n];
30         }
31         return temp;
32     }
33 };

2.2 Java

 1 class Solution {
 2     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3         int n1 = nums1.length, n2 = nums2.length;
 4         int[] obj = new int[n1 + n2]; 
 5         double temp = 0.0;
 6         int i = 0, j = 0, k = 0;
 7         while(i < n1 || j < n2){
 8             if(i != n1 && j != n2){
 9                 if(nums1[i] <= nums2[j]){
10                     obj[k] = nums1[i];
11                     i++;
12                 }else{
13                     obj[k] = nums2[j];
14                     j++;
15                 }
16             }else if(i == n1){
17                 obj[k] = nums2[j];
18                 j++;
19             }else if(j == n2){
20                 obj[k] = nums1[i];
21                 i++;
22             }
23             k++;
24         }
25         int n = (n1 + n2) / 2;
26         if((n1 + n2) % 2 == 0){
27             temp = (obj[n - 1] + obj[n]) / 2.0;
28         }else{
29             temp = obj[n];
30         }
31         return temp;
32     }
33 }

2.3 Python

 1 class Solution:
 2     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
 3         nums1.extend(nums2)
 4         nums1.sort()
 5         n = len(nums1)
 6         k = int(n / 2)
 7         if(n % 2 == 0):
 8             temp = (nums1[k - 1] + nums1[k]) / 2.0
 9         else:
10             temp = nums1[k]
11         return temp 
12             

3. 结语

     努力去爱周围的每一个人,付出,不一定有收获,但是不付出就一定没有收获! 给街头卖艺的人零钱,不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)!

     如果客官喜欢小生的园子,记得关注小生哟,小生会持续更新(#^.^#)(#^.^#)。

原文地址:https://www.cnblogs.com/haifwu/p/13780450.html