七刷 07/2022
Version #1 Binary Search
这里的findKth写的是0indexed的方法，比较符合常规，但是在k = 1的时候k - k/2还是1会进入infinite loop
所以此处的base case是k=0和k=1
注意k=0的时候是从nums1[start1]和nums2[start2]里面取最小，这个是正确的
但是k=1的时候就是从nums1[start1] nums1[start1 + 1] nums2[start2] nums2[start2 + 1]四个数里面取第二大，所以需要特殊处理
Time O(log(M + N))
Space O(1)
Runtime: 9 ms, faster than 20.19% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 50.4 MB, less than 19.16% of Java online submissions for Median of Two Sorted Arrays.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if (len % 2 == 0) {
// 0 1
return 1.0 * (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 - 1)) / 2;
}
// 0 1 2
return findKth(nums1, 0, nums2, 0, len / 2);
}
private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
// System.out.printf("start1=%d, start2=%d, k=%d\n", start1, start2, k);
if (start1 >= nums1.length) {
return nums2[start2 + k];
}
if (start2 >= nums2.length) {
return nums1[start1 + k];
}
if (k == 0) {
return Math.min(nums1[start1], nums2[start2]);
}
if (k == 1) {
List<Integer> temp = new ArrayList<>();
temp.add(nums1[start1]);
if (start1 + 1 < nums1.length) {
temp.add(nums1[start1 + 1]);
}
temp.add(nums2[start2]);
if (start2 + 1 < nums2.length) {
temp.add(nums2[start2 + 1]);
}
Collections.sort(temp);
return temp.get(1);
}
// nums1[start1 + k / 2]
// nums2[start2 + k / 2]
int n1 = start1 + k / 2 < nums1.length ? nums1[start1 + k / 2] : Integer.MAX_VALUE;
int n2 = start2 + k / 2 < nums2.length ? nums2[start2 + k / 2] : Integer.MAX_VALUE;
if (n1 < n2) {
return findKth(nums1, start1 + k / 2, nums2, start2, k - k / 2);
}
return findKth(nums1, start1, nums2, start2 + k / 2, k - k / 2);
}
}
六刷
Runtime: 4 ms, faster than 58.19% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 50 MB, less than 31.58% of Java online submissions for Median of Two Sorted Arrays.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null) {
nums1 = new int[0];
}
if (nums2 == null) {
nums2 = new int[0];
}
int len = nums1.length + nums2.length;
if (len % 2 == 1) { // e.g. [2] -> find the 1st
return findKth(nums1, 0, nums2, 0, len / 2 + 1) * 1.0;
} else {
// e.g. [1, 2] -> find the 1st and 2nd, len = 2
return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
}
}
private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
if (start1 >= nums1.length) {
return nums2[start2 + k - 1];
}
if (start2 >= nums2.length) {
return nums1[start1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
// len = 4, k = 2 (and 3)
// k / 2 = 1, start1 = 0, start2 = 0
// nums1 [1, 2]
// nums2 [3, 4]
// When trying to find the 2nd element, we should try to deprecate k/2 element
// if start1 + k/2 is larger than the length of nums1
// we could deprecate the 1st k/2 of nums2
if (start1 + k / 2 - 1 >= nums1.length) {
start2 += k / 2;
} else if (start2 + k / 2 - 1 >= nums2.length) {
start1 += k/2;
} else if (nums1[start1 + k / 2 - 1] <= nums2[start2 + k / 2 - 1]) {
start1 += k / 2;
} else {
start2 += k / 2;
}
return findKth(nums1, start1, nums2, start2, k - k / 2);
}
}
五刷
把题目转换成find Kth element
log(m + n), every time deprecate k/2 element
find k=5th element, deprecate 2 elements, k/2=2
k - k/2 = 3
we'll be looking for the 3rd element in the new arrays
7
3 6
for two arrays
Check the k/2 element in the array
If A[k/2] < B[k/2], for A array, there are only k/2 elements smaller than A[k/2], so that first half can be deprecated
An, An+1, An+2, ...
Bm, Bm+1, Bm+2,...
Runtime: 2 ms, faster than 99.87% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.5 MB, less than 26.02% of Java online submissions for Median of Two Sorted Arrays.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// findKthElement
int len = nums1.length + nums2.length;
// e.g. len = 2
if (len % 2 == 0) {
return (findKthElement(nums1, 0, nums2, 0, len / 2) + findKthElement(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
} else {
// e.g. len = 3 want 2nd
// e.g. len = 1 want 1st
return findKthElement(nums1, 0, nums2, 0, len / 2 + 1);
}
}
private int findKthElement(int[] nums1, int start1, int[]nums2, int start2, int k) {
// System.out.printf("start1->%d, start2->%d, k->%d\n", start1, start2,k);
if (start1 >= nums1.length) {
return nums2[start2 + k - 1];
}
if (start2 >= nums2.length) {
return nums1[start1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
// try to deprecate 2/k smallest element
int c1 = start1 + k / 2 - 1 < nums1.length? nums1[start1 + k / 2 - 1]: Integer.MAX_VALUE;
int c2 = start2 + k / 2 - 1 < nums2.length ? nums2[start2 + k / 2 - 1]: Integer.MAX_VALUE;
// System.out.printf("c1->%d, c2->%d\n", c1, c2);
if (c1 < c2) {
// start1 = 0, start2 = 0,
return findKthElement(nums1, start1 + k/2, nums2, start2, k - k / 2);
} else {
return findKthElement(nums1, start1, nums2, start2 + k/2, k - k / 2);
}
}
}
44.08 %
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int size = nums1.length + nums2.length;
if (size % 2 == 0) {
return (helper(nums1, 0, nums2, 0, size / 2)
+ helper(nums1, 0, nums2, 0, size / 2 + 1)) / 2.0;
} else {
return (double)helper(nums1, 0, nums2, 0, size / 2 + 1);
}
}
private int helper(int[] nums1, int head1, int[] nums2, int head2, int k) {
// Find the smallest number
if (head1 + k / 2 - 1 >= nums1.length) {
return helper(nums1, head1, nums2, head2 + k / 2, k - k / 2);
}
if (head2 + k / 2 - 1 >= nums2.length) {
return helper(nums1, head1 + k / 2, nums2, head2, k - k / 2);
}
if (k == 1) {
if (head1 >= nums1.length) {
return nums2[head2];
}
if (head2 >= nums2.length) {
return nums1[head1];
}
return Math.min(nums1[head1], nums2[head2]);
}
// e.g. k = 2
int temp1 = nums1[head1 + k / 2 - 1];
int temp2 = nums2[head2 + k / 2 - 1];
if (temp1 < temp2) {
return helper(nums1, head1 + k / 2, nums2, head2, k - k / 2);
} else {
return helper(nums1, head1, nums2, head2 + k / 2, k - k / 2);
}
}
}
三刷
竟然还是做不出来
思路是从前往后删
单边删
if (aStart > A.length - 1) return B[bStart + k - 1]; // in the case, all element in array A has been checked and ignored like a 0 size array , the find kth element in A, B is equivalent to find kth just in B (start from bStart)
if (bStart > B.length - 1) return A[aStart + k - 1];
if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; //A, B are different size array, only if the index<array.Length, the index will be valid, otherwise, set mid to int.Max, so we will always keep the left part(low index) of array
if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1]; 二刷
k==1必须作为base case 因为k / 2 == 0，相当于没有办法排除任何数，就会进入死循环
导致这个的原因是一开始我把helper函数定义为找第k小，而不是前k小，也就是说k == 0才是base case
而比较清楚的定义方法是寻找前k小
当k==1的时候就是找最小的
e.g.length == 3
3 / 2 = 1
index 0 1 2
希望找到Index = 1的数，然而它实际上是前length / 2 + 1 = 2大的数
e.g. length == 4
4 / 2 = 2
index 0 1 2 3
we want to find (index1 + index 2) / 2
-> (第2大 + 第3大) / 2
所以是length/ 2 和length / 2 + 1
比较绕
反正就是对k做整除时候，特别警惕k==1的情况，因为这时k/2 == 0容易进入死循环
如果两个mid相等不能直接Return
因为譬如
[1, 2]
[1, 2]
要找3
发现currA = currB = 1
但实际上它们只是前 2
54.82 %
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) return -1.0;
int length = nums1.length + nums2.length;
if (length % 2 == 1) {
return findMedianSortedArrays(nums1, 0, nums2, 0, length / 2 + 1);
} else {
return (findMedianSortedArrays(nums1, 0, nums2, 0, length / 2)
+ findMedianSortedArrays(nums1, 0, nums2, 0, length / 2 + 1)) / 2.0;
}
}
//find the kth element of A[indexA, lengthA - 1], B[indexB, lengthB - 1]
private double findMedianSortedArrays(int[] A, int indexA, int[] B, int indexB, int k) {
//System.out.println("indexA " + indexA + " indexB " + indexB + " k " + k);
if (indexA >= A.length) return B[indexB + k - 1];
if (indexB >= B.length) return A[indexA + k - 1];
if (k == 1) return Math.min(A[indexA], B[indexB]);
int currA = indexA + k / 2 - 1 >= A.length ? Integer.MAX_VALUE : A[indexA + k / 2 - 1];
int currB = indexB + k / 2 - 1 >= B.length ? Integer.MAX_VALUE : B[indexB + k / 2 - 1];
if (currA < currB) {
return findMedianSortedArrays(A, indexA + k / 2, B, indexB, k - k / 2);
} else {
return findMedianSortedArrays(A, indexA, B, indexB + k / 2, k - k / 2);
}
}
}
思路就是Binary Search 时间复杂度是logk
但是这种处理Index的各种floor division的case简直要疯了啊啊啊啊啊啊啊啊啊！
还有subString那种各种index啊啊啊啊啊啊啊！
淡定淡定
class Solution {
/**
* @param A: An integer array.
* @param B: An integer array.
* @return: a double whose format is *.5 or *.0
*/
public double findMedianSortedArrays(int[] A, int[] B) {
// write your code here
int length = A.length + B.length;
if (length % 2 == 1) {
return findKthElement(A, 0, B, 0, length / 2 + 1);
} else {
return (findKthElement(A, 0, B, 0, length / 2) + findKthElement(A, 0, B, 0, length / 2 + 1)) / 2.0;
}
}
private int findKthElement(int[] A, int indexA, int[] B, int indexB, int k) {
if (indexA >= A.length) return B[indexB + k - 1];
if (indexB >= B.length) return A[indexA + k - 1];
if (k == 1) return Math.min(A[indexA], B[indexB]);
int currA = (indexA + k / 2 - 1 >= A.length) ? Integer.MAX_VALUE : A[indexA + k / 2 - 1];
int currB = (indexB + k / 2 - 1 >= B.length) ? Integer.MAX_VALUE : B[indexB + k / 2 - 1];
if (currA < currB) {
return findKthElement(A, indexA + k / 2, B, indexB, k - k / 2);
} else {
return findKthElement(A, indexA, B, indexB + k / 2, k - k / 2);
}
}
}
No comments:
Post a Comment