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)).
看到这题,本来是想寻找每一部分的中间值进行分治想法来解决的。但是写了半天,发现自己实现的特别乱,而且自己的想法也是错误的,于是只能用最暴力的方式来解决,即排序在寻找中位数,
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
double end = 0.0;
int length = A.length+B.length;
int[] c = new int[length];
int j = 0;
int k = 0;
for(int i = 0;i<length;i++){
if(A.length != 0 && B.length != 0){
if(j<A.length&&k<B.length&&A[j]<=B[k]){
c[i] = A[j];
j++;
}else if(j<A.length&&k<B.length){
c[i] = B[k];
k++;
}else if(j==A.length){
c[i] = B[k];
k++;
}else if(k == B.length){
c[i] = A[j];
j++;
}
}else if(A.length>0 && B.length == 0){
c[i] = A[i];
}else {
c[i] = B[i];
}
}
end = c.length%2 == 0?(c[c.length/2-1]+c[c.length/2])*0.5:c[c.length/2];
return end;
}
}
但这个明显不是一个最好的方式,因为其时间复杂度是O(m+n),但似乎leetcode并不检查这个,所以还是通过了,时间是377ms。于是在网上找到了一个比较好的解法。
http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/
既可以将问题转化为寻找第Kth个元素。数组A[M]和数组B[N]有sum = M+N个元素,若sum为奇数,即为寻找组合后的第K=sum/2+1 元素,若为偶数,既可以转换为寻找第K = sum/2 和K+1个元素。之后就可以用二分法进行寻找,既比较两个数组中的加权平均后的第Kth个值,即A[]中的第k*m/(m+n) 个值和B[]中的第k*n/(m+n),比较这两个值,其中较小的可以舍弃,因为所寻找的第K个元素肯定不会在其中,如此一直二分下去,最终的时间复杂度为O(log(m+n)).
public static double findMedianSortedArrays(int A[], int B[]) {
int m = A.length;
int n = B.length;
if ((m + n) % 2 != 0) // odd
return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
else { // even
return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1)
+ findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
}
}
public static int findKth(int A[], int B[], int k,
int aStart, int aEnd, int bStart, int bEnd) {
int aLen = aEnd - aStart + 1;
int bLen = bEnd - bStart + 1;
// Handle special cases
if (aLen == 0)
return B[bStart + k];
if (bLen == 0)
return A[aStart + k];
if (k == 0)
return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
int aMid = aLen * k / (aLen + bLen); // a's middle count
int bMid = k - aMid - 1; // b's middle count
// make aMid and bMid to be array index
aMid = aMid + aStart;
bMid = bMid + bStart;
if (A[aMid] > B[bMid]) {
k = k - (bMid - bStart + 1);
aEnd = aMid;
bStart = bMid + 1;
} else {
k = k - (aMid - aStart + 1);
bEnd = bMid;
aStart = aMid + 1;
}
return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}
看到这题,本来是想寻找每一部分的中间值进行分治想法来解决的。但是写了半天,发现自己实现的特别乱,而且自己的想法也是错误的,于是只能用最暴力的方式来解决,即排序在寻找中位数,
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
double end = 0.0;
int length = A.length+B.length;
int[] c = new int[length];
int j = 0;
int k = 0;
for(int i = 0;i<length;i++){
if(A.length != 0 && B.length != 0){
if(j<A.length&&k<B.length&&A[j]<=B[k]){
c[i] = A[j];
j++;
}else if(j<A.length&&k<B.length){
c[i] = B[k];
k++;
}else if(j==A.length){
c[i] = B[k];
k++;
}else if(k == B.length){
c[i] = A[j];
j++;
}
}else if(A.length>0 && B.length == 0){
c[i] = A[i];
}else {
c[i] = B[i];
}
}
end = c.length%2 == 0?(c[c.length/2-1]+c[c.length/2])*0.5:c[c.length/2];
return end;
}
}
但这个明显不是一个最好的方式,因为其时间复杂度是O(m+n),但似乎leetcode并不检查这个,所以还是通过了,时间是377ms。于是在网上找到了一个比较好的解法。
http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/
既可以将问题转化为寻找第Kth个元素。数组A[M]和数组B[N]有sum = M+N个元素,若sum为奇数,即为寻找组合后的第K=sum/2+1 元素,若为偶数,既可以转换为寻找第K = sum/2 和K+1个元素。之后就可以用二分法进行寻找,既比较两个数组中的加权平均后的第Kth个值,即A[]中的第k*m/(m+n) 个值和B[]中的第k*n/(m+n),比较这两个值,其中较小的可以舍弃,因为所寻找的第K个元素肯定不会在其中,如此一直二分下去,最终的时间复杂度为O(log(m+n)).
public static double findMedianSortedArrays(int A[], int B[]) {
int m = A.length;
int n = B.length;
if ((m + n) % 2 != 0) // odd
return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
else { // even
return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1)
+ findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
}
}
public static int findKth(int A[], int B[], int k,
int aStart, int aEnd, int bStart, int bEnd) {
int aLen = aEnd - aStart + 1;
int bLen = bEnd - bStart + 1;
// Handle special cases
if (aLen == 0)
return B[bStart + k];
if (bLen == 0)
return A[aStart + k];
if (k == 0)
return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
int aMid = aLen * k / (aLen + bLen); // a's middle count
int bMid = k - aMid - 1; // b's middle count
// make aMid and bMid to be array index
aMid = aMid + aStart;
bMid = bMid + bStart;
if (A[aMid] > B[bMid]) {
k = k - (bMid - bStart + 1);
aEnd = aMid;
bStart = bMid + 1;
} else {
k = k - (aMid - aStart + 1);
bEnd = bMid;
aStart = aMid + 1;
}
return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}
发表评论
-
Merge k Sorted Lists
2015-03-12 19:55 323Merge k sorted linked lists and ... -
Generate Parentheses
2015-03-12 19:50 363Given n pairs of parentheses, w ... -
Generate Parentheses
2015-03-05 22:39 0Given n pairs of parentheses, w ... -
Valid Parentheses
2015-03-05 22:33 306Given a string containing just ... -
Remove Nth Node From End of List
2015-03-05 22:31 336Given a linked list, remove the ... -
Letter Combinations of a Phone Number
2015-03-05 22:30 327Letter Combinations of a Phone ... -
4Sum
2015-03-05 22:26 309Given an array S of n integers, ... -
3Sum Closest
2015-03-05 22:25 287Given an array S of n integers, ... -
3Sum
2015-03-03 22:34 316Given an array S of n integers, ... -
Longest Common Prefix
2015-03-03 22:21 324Write a function to find the lo ... -
Roman to Integer
2015-03-03 22:20 324Given a roman numeral, convert ... -
Integer to Roman
2015-03-01 23:35 287Given an integer, convert it to ... -
Container With Most Water
2015-03-01 22:55 319Given n non-negative integers a ... -
Regular Expression Matching
2015-03-01 20:19 362Implement regular expression ma ... -
Palindrome Number
2015-02-13 22:08 329Determine whether an integer is ... -
String to Integer (atoi)
2015-02-13 11:07 336Implement atoi to convert a str ... -
Reverse Integer
2015-02-12 23:39 224Reverse digits of an integer. ... -
ZigZag Conversion
2015-02-12 23:37 251The string "PAYPALISHIRING ... -
Longest Palindromic Substring
2015-02-12 22:50 330Given a string S, find the long ... -
Add Two Numbers
2015-02-12 22:12 297You are given two linked lists ...
相关推荐
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 ...