http://oj.leetcode.com/problems/median-of-two-sorted-arrays/
There are two sorted arrays A and B 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)).
思路:
(1)时间复杂度O(log(m+n)),联想到递归法;
(2)问题形式化为:查找两个数组的第K大小的数findKth(A, m, B, n, topK);
(3)边界条件:凡是出现了加、减的地方都要考虑数组的上下界;
(4)两个数组大小不一样,计算机只解决一次就行,不用分开考虑。在函数头部加上调整数组顺序即可。
class Solution {
public:
double findKth(int A[], int m, int B[], int n, int topK) {
// always assume that m is equal or less than n
if (m > n) {
return findKth(B, n, A, m, topK);
}
if(m == 0) {
return B[topK - 1];
}
if (topK == 1) {
return min(A[0], B[0]);
}
// divide topK into two parts
int pa = min(topK/2, m);
int pb = topK - pa;
if (A[pa-1] < B[pb-1]){
return findKth(A+pa, m-pa, B, n, topK - pa);
} else if (A[pa-1] > B[pb-1]) {
return findKth(A, m, B+pb, n-pb, topK - pb);
} else {
return A[pa-1];
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if ((m+n)%2 == 1) {
return findKth(A, m, B, n, (m+n)/2 + 1) * 1.0;
} else {
return (findKth(A, m, B, n, (m+n)/2) +
findKth(A, m, B, n, (m+n)/2 + 1)) * 1.0 / 2;
}
}
};
分享到:
相关推荐
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版本
js代码-4. Median of Two Sorted Arrays
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 ...
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...
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 ...
Two Sum 002. Add Two Numbers 003. Longest Substring Without Repeating Characters4. Median of Two Sorted Arrays 004. Median of Two Sorted Arrays 005. Longest Palindromic Substring 006. ZigZag ...
Two Sum.cpp │ │ ├── 002 - Add Two Numbers.cpp │ │ ├── 003 - Longest Substring Without Repeating Characters.cpp │ │ ├── 004 - Median of Two Sorted Arrays.cpp │ │ └──...
Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 12. Integer to Roman 13. Roman to Integer 14. Longest Common Prefix ...
Median of Two Sorted Arrays 困难 数学 Longest Palindromic Substring 中等 回文 ZigZag Conversion 中等 矩阵 重要 Reverse Integer 简单 字串 String to Integer (atoi) 中等 字串 麻烦 Palindrome Number 简单 ...
#4:Median of Two Sorted Arrays 地图 #1:Two Sum #3:Longest Substring Without Repeating Characters #5:Longest Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:...
Median of Two Sorted Arrays 30.7% Hard 0005 Longest Palindromic Substring 30.1% Medium 0006 ZigZag Conversion 37.5% Medium 0007 Reverse Integer 25.8% Easy 0008 String to Integer (atoi) 15.5% Medium ...
Median of Two Sorted Arrays 递归实现find kth 6 Longest Consecutive Sequence 7 Two Sum Hash,夹逼均可 8 3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next ...
4.Median of Two Sorted Arrays 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 11.Container With Most Water 14.Longest Common Prefix 15.3Sum 16.3Sum Closest 19.Remove Nth Node From End...
4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 10.Regular Expression Matching ...
Median of Two Sorted Arrays (寻找两个有序数组的中位数) Hard Divide and Conquer 5 Longest Palindromic Substring (最长回文子串) Medium Dynamic Programming 7 Reverse Integer (整数反转) Easy Math 8 String...
leetcode 2sum ...Median Of Two Sorted Arrays [Hard] LC6: Zigzag Conversion [Medium] LC7: Reverse Integer [Easy] LC8: String To Integer Atoi [Medium] LC9: Palindrome Number [Easy] LC11:
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 ...
Median of Two Sorted Arrays 36.3% 困难 5 Longest Palindromic Substring 27.6% 中等 6 ZigZag Conversion 45.6% 中等 7 Reverse Integer 33.2% 简单 8 String to Integer (atoi) 18.5% 中等 9 Palindrome Number ...