另一种方法即是利用类似merge的操作找到中位数,利用两个分别指向A和B数组头的指针去遍历数组,然后统计元素个数,直到找到中位数,此时算法复杂度为O(n)。之后还尝试了根据算法导论中的习题(9.3-8)扩展的方法,但是该方法会存在无穷多的边界细节问题,而且扩展也不见得正确,这个可从各网页的评论看出,非常不建议大家走这条路。
最后从medianof two sorted arrays中看到了一种非常好的方法。原文用英文进行解释,在此我们将其翻译成汉语。该方法的核心是将原问题转变成一个寻找第k小数的问题(假设两个原序列升序排列),这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题,原问题也得以解决。
首先假设数组A和B的元素个数都大于k/2,我们比较A[k/2-1]和B[k/2-1]两个元素,这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况:>、<和=。如果A[k/2-1]<B[k/2-1],这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
证明也很简单,可以采用反证法。假设A[k/2-1]大于合并之后的第k小值,我们不妨假定其为第(k+1)小值。由于A[k/2-1]小于B[k/2-1],所以B[k/2-1]至少是第(k+2)小值。但实际上,在A中至多存在k/2-1个元素小于A[k/2-1],B中也至多存在k/2-1个元素小于A[k/2-1],所以小于A[k/2-1]的元素个数至多有k/2+ k/2-2,小于k,这与A[k/2-1]是第(k+1)的数矛盾。
当A[k/2-1]>B[k/2-1]时存在类似的结论。
当A[k/2-1]=B[k/2-1]时,我们已经找到了第k小的数,也即这个相等的元素,我们将其记为m。由于在A和B中分别有k/2-1个元素小于m,所以m即是第k小的数。(这里可能有人会有疑问,如果k为奇数,则m不是中位数。这里是进行了理想化考虑,在实际代码中略有不同,是先求k/2,然后利用k-k/2获得另一个数。)
通过上面的分析,我们即可以采用递归的方式实现寻找第k小的数。此外我们还需要考虑几个边界条件:
- 如果A或者B为空,则直接返回B[k-1]或者A[k-1];
- 如果k为1,我们只需要返回A[0]和B[0]中的较小值;
- 如果A[k/2-1]=B[k/2-1],返回其中一个;
最终实现的代码为:
- double findKth(int a[], int m, int b[], int n, int k)
- {
- //always assume that m is equal or smaller than n
- if (m > n)
- return findKth(b, n, a, m, k);
- if (m == 0)
- return b[k - 1];
- if (k == 1)
- return min(a[0], b[0]);
- //divide k into two parts
- int pa = min(k / 2, m), pb = k - pa;
- if (a[pa - 1] < b[pb - 1])
- return findKth(a + pa, m - pa, b, n, k - pa);
- else if (a[pa - 1] > b[pb - 1])
- return findKth(a, m, b + pb, n - pb, k - pb);
- else
- return a[pa - 1];
- }
- class Solution
- {
- public:
- double findMedianSortedArrays(int A[], int m, int B[], int n)
- {
- int total = m + n;
- if (total & 0x1)
- return findKth(A, m, B, n, total / 2 + 1);
- else
- return (findKth(A, m, B, n, total / 2)
- + findKth(A, m, B, n, total / 2 + 1)) / 2;
- }
- };
我们可以看出,代码非常简洁,而且效率也很高。在最好情况下,每次都有k一半的元素被删除,所以算法复杂度为logk,由于求中位数时k为(m+n)/2,所以算法复杂度为log(m+n)。
转自:http://blog.csdn.net/yutianzuijin/article/details/11499917/
相关推荐
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)). Java AC版本
java java_leetcode题解之Median of Two Sorted Arrays.java
java入门 java_leetcode题解之004_Median_of_Two_Sorted_Arrays
js js_leetcode题解之4-median-of-two-sorted-arrays.js
c语言入门 c语言_leetcode题解04-median-of-two-sorted-arrays.c
leetcode 无法登录两个有序数组的中位数 问题 有两个大小分别为 m 和 n 的排序数组 nums1 和 nums2。求两个排序数组的中位数。 整体运行时间复杂度应该是 O(log (m+n))。 您可以假设 nums1 和 nums2 不能都为空。 ...
4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum ...
leetcode Python 001 leetcode的算法问题 这是我的解决方案,用 cpp 、 java 和 python 编写 #LeetCode 解决的问题: 001. Two Sum 002. Add Two Numbers 003. Longest Substring Without Repeating Characters4. ...
leetcode分类LeetCodeSourceCodes###LeetCode1TowSum如果数组是有序的,O(n)的时间复杂度就可以解决了,现在是无序的,一开始要排一下序###LeetCode2MedianofTwoSortedArrays让用logn的时间复杂度,用了两个二分,...
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. ...
leetcode Python 001 力码 ├── Algorithms │ ├── cpp │ │ ├── 001 - Two Sum.cpp │ │ ├── 002 - Add Two Numbers.cpp │ │ ├── 003 - Longest Substring Without Repeating ...
7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two ...
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: leetcode 代码库,我博客上的解题思路: mkdir 列表: 大批 #1:Two Sum #4:Median of Two Sorted Arrays 地图 #1:Two Sum #3:...
在LeetCode上,题目4(Median of Two Sorted Arrays)是一个经典的算法问题,旨在寻找两个已排序数组的中位数。中位数是将一组数值从小到大排列后处于中间位置的数,在奇数个数的情况下是中间的那个数,而在偶数个数...
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
记录自己Leetcode之旅 排序类(Sort)[x]: 基础知识:快速排序(Quick Sort), 归并排序(Merge Sort)的原理与代码实现。需要能讲明白代码中每一行的目的。快速排序时间复杂度平均状态下O(NlogN),空间复杂度O...
leetcode 2 Leetcode答案集 关于项目: 本项目包含本人LeetCode解题的答案,全部将由JavaScript语言进行解答。并会在每个题目的文件夹中添加相关的思路解析。 详情 # Title Solution Time Space Difficulty 1 Two ...
* 两个排序数组的中位数(Median of Two Sorted Arrays):计算两个排序数组的中位数。 * 整数到罗马(Integer to Roman):将整数转换为罗马数字。 * 罗马到整数(Roman to Integer):将罗马数字转换为整数。 4...
Median of Two Sorted Arrays 5 Longest Palindromic Substring 8 String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove ...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....