当前位置: 代码迷 >> 综合 >> LeetCode4. Median of Two Sorted Arrays
  详细解决方案

LeetCode4. Median of Two Sorted Arrays

热度:85   发布时间:2023-12-12 18:41:56.0

之前没钻研过LeetCode,上次做题时,以为要找什么类型的题目就在搜索栏输入对应的关键词,结果输入divide-and-conquer才搜到一题,后来经提醒才知道在网页右侧有个提供各种关键词的topics框部,点击了divide-and-conquer便搜到了好多道相关题目,方便许多。之前真是太蠢了。

这次选择的是第4题:Median of Two Sorted Arrays 难度系数为Hard。

题目要求如下:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]The median is (2 + 3)/2 = 2.5


最先想到的、即最容易的方法便是将两个数组合并,重新排序,然后根据奇偶顺利找出中位数。代码如下:

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();vector<int> All_array;//将两个数组合并All_array.assign(nums1.begin(), nums1.end());All_array.insert(All_array.end(), nums2.begin(), nums2.end());//将合并后的数组进行排序sort(All_array.begin(), All_array.end());return (m+n)%2?All_array[(m+n)/2]:(All_array[(m+n)/2-1]+All_array[(m+n)/2])/2.0;}
};


然而此题的难度便在于题目要求将时间复杂度限制在O(log(m+n)),也就是在暗示我们采取分治法。首先保持两个原数组不变,相当于首次一分为二。那么接下来要怎么再逐步分下去呢?我们可以想办法将所有的数据分为两部分:1 含有中位数的部分数据; 2 不含中位数的部分数据。然后将没用的第2部分数据抛弃,再将有用的第1部分数据继续递归分裂,直至筛选出中位数。

那么问题来了。

将所有数据分为两部分,如何确定中位数存在于哪部分呢?

我们也可以将该问题扩展,设0<k<m+n,将所有数据分为两部分,那如何确定第k大的数存在于哪部分呢?我们将这个第k大的数字称为“int_K”。

【以下皆按正常情况进行讨论】

首先,两个数组都是已排序好的。在所有的数据中,若按从小到大进行排序,int_K前面应有k-1个数。

我们在nums1中取nums1[0]到nums1[k/2-1]共k/2个整数(从小到大),在nums2中取nums2[0]到nums2[k/2-1]共k/2个整数(从小到大)。

【反证法】 若nums1[k/2-1]≥nums1[k/2-1],如果int_K存在于nums2[0]~nums2[k/2-1]之中,那么所有数据按大小,排在int_K前面的仅可能是nums1[0]~nums1[k/2-2]和nums2[0]~nums2[k/2-2],加起来的总数绝不超过k-1,这与“int_K前面应有k-1个数”矛盾。故int_K不存在于nums2[0]到nums2[k/2-1]之中,可将这部分数据抛弃。反之如此。

按此思路,代码如下:

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();if ((m + n) % 2) return find_kth_SortedArrays(nums1, nums2, (m + n) / 2 + 1);elsereturn (find_kth_SortedArrays(nums1, nums2, (m + n) / 2) + find_kth_SortedArrays(nums1, nums2, (m + n) / 2 + 1)) / 2.0;}int find_kth_SortedArrays(vector<int> nums1, vector<int> nums2, int k) {int m = nums1.size();int n = nums2.size();if (m > n)return find_kth_SortedArrays(nums2, nums1, k);if (m == 0)return nums2[k - 1];if (k == 1)return min(nums1[0], nums2[0]);int temp1 = min(m, k/2);int temp2 = min(n, k/2);if (nums1[temp1 - 1] >= nums2[temp2 - 1]) {return find_kth_SortedArrays(nums1, vector<int>(nums2.begin() + temp2, nums2.end()), k - temp2);} else {return find_kth_SortedArrays(vector<int>(nums1.begin() + temp1, nums1.end()), nums2, k - temp1);}return 0;}
};

另外我又尝试了别的方法,也是寻找第k位大的数。该方法即针对每个选定的数据,判断在所有的数据当中,是否存在k-1个数字小于等于它,其他的数字都大于等于它。若是,则返回该数据。代码如下(根据多种情况不停填补修改 所以代码看着有点乱= =)

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();return (find_kth_SortedArrays(nums1, nums2, (m + n + 1) / 2) + find_kth_SortedArrays(nums1, nums2, (m + n + 2) / 2)) / 2.0;}int find_kth_SortedArrays(vector<int> nums1, vector<int> nums2, int k) {int m = nums1.size();int n = nums2.size();if (m == 0)return nums2[k - 1];if (n == 0)return nums1[k - 1];if (k == 1)return min(nums1[0], nums2[0]);int i;for (i = 0; i < m; i++) {if (k-1-i-1 >= 0 && k-1-i-1 < n && nums2[k-1-i-1] <= nums1[i]) {if (k-1-i >= n)return nums1[i];else if (nums2[k-1-i] >= nums1[i])return nums1[i];}if (k == i + 1 && nums2[0] >= nums1[i])return nums1[i];}for (i = 0; i < n; i++) {if (k-1-i-1 >= 0 && k-1-i-1 < m && nums1[k-1-i-1] <= nums2[i]) {if (k-1-i >= m)return nums2[i];else if (nums1[k-1-i] >= nums2[i])return nums2[i];}if (k == i + 1 && nums1[0] >= nums2[i])return nums2[i];}}
};







  相关解决方案