4. Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
Solution:
Two Pointer:
Binary Search:
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int len = len1 + len2;
if (len1 > len2){
return findMedianSortedArrays(nums2, nums1);
}
int left = 0;
int right = len1;
// value for the left right boundary of nums
int l1 = 0;
int r1 = 0;
int l2 = 0;
int r2 = 0;
while(left <= right){
int mid1 = left + (right - left)/2;
int mid2 = (len + 1)/ 2 - mid1; // 6 - 2 = 4
// 加 1 是为了处理当元素总数为奇数的情况，使得左半部分比右半部分多一个元素。无论总数是奇数还是偶数，这个分割线都能正确分割数组
// (m + n + 1) / 2 - i;
// 5 + 8 + 1 /2 -3
// 13+1 = 14 /2 = 7 - 3 = 4
if (mid1 == 0){
l1 = Integer.MIN_VALUE;
}else {
l1 = nums1[mid1 -1];
}
if (mid1 == len1){
r1 = Integer.MAX_VALUE;
}else {
r1 = nums1[mid1];
}
if (mid2 == 0){
l2 = Integer.MIN_VALUE;
}else{
l2 = nums2[mid2 - 1];
}
if (mid2 == len2){
r2 = Integer.MAX_VALUE;
}else{
r2 = nums2[mid2];
}
// check 是否满足正确的分割条件
if (l1 <= r2 && l2 <= r1){
if ((len) % 2 == 0){
return ((double) Math.max(l1, l2) + Math.min(r1, r2)) /2.0;
}else{
return Math.max(l1, l2);
}
}else if (l1 > l2){
right = mid1 - 1;
}else{
left = mid1 + 1;
}
}
return -1;
}
}
// TC: O(log(min(m,n)))
// SC: O(1)
嗯...两天啥也没干是吧...
I am back again
Back again 还是不会
Two Pointers:
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums = new int[nums1.length + nums2.length];
int i = 0;
int j = 0;
int k = 0;
while (i < nums1.length && j < nums2.length){
if (nums1[i] < nums2[j]){
nums[k] = nums1[i];
k++;
i++;
}else {
nums[k] = nums2[j];
k++;
j++;
}
}
while(i < nums1.length){
nums[k] = nums1[i];
k++;
i++;
}
while(j < nums2.length){
nums[k] = nums2[j];
k++;
j++;
}
int mid = nums.length / 2;
if (nums.length % 2 == 0){
return (nums[mid - 1] + nums[mid] )/2.0;
}else{
return nums[mid];
}
}
}
// TC: O(n + m)
// SC: O(n + m)
虽然能过 但其实是不满足题意的
https://www.youtube.com/watch?v=q6IEA26hvXc
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int half = (nums1.length +nums2.length)/2;
if(nums2.length <nums1.length){
return findMedianSortedArrays(nums2,nums1);
}
int left = 0;
int right = nums1.length-1;
while(true){
int mid1 =(int)Math.floor((right+left)/2.0);
int mid2 = half -(mid1+1)-1;
int l1 = mid1>=0?nums1[mid1]:Integer.MIN_VALUE;
int l2 = mid2>=0?nums2[mid2]:Integer.MIN_VALUE;
int r1 = (mid1+1)<nums1.length?nums1[mid1+1]:Integer.MAX_VALUE;
int r2 = (mid2+1)<nums2.length?nums2[mid2+1]:Integer.MAX_VALUE;
if(l1<=r2 && l2<=r1 ){
//found it
if((nums1.length+nums2.length) %2 ==0){
return ((double)Math.max(l1,l2) +(double)Math.min(r1,r2))/2.0;
}else{
return Math.min(r1,r2);
}
}
else if(l1>r2){
right = mid1-1;
}else{
left = mid1+1;
}
}
}
}
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Ensure nums1 is the smaller array
if (nums2.length < nums1.length) {
return findMedianSortedArrays(nums2, nums1);
}
int totalLength = nums1.length + nums2.length;
int half = totalLength / 2;
l1
int left = 0;
int right = nums1.length - 1;
// Use 'while (left <= right)'
while (left <= right) {
int mid1 = left + (right - left) / 2;
int mid2 = half - (mid1 + 1) - 1;
int l1 = (mid1 >= 0) ? nums1[mid1] : Integer.MIN_VALUE;
int l2 = (mid2 >= 0) ? nums2[mid2] : Integer.MIN_VALUE;
int r1 = (mid1 + 1 < nums1.length) ? nums1[mid1 + 1] : Integer.MAX_VALUE;
int r2 = (mid2 + 1 < nums2.length) ? nums2[mid2 + 1] : Integer.MAX_VALUE;
// Check if correct partition is found
if (l1 <= r2 && l2 <= r1) {
if (totalLength % 2 == 0) {
return ((double) Math.max(l1, l2) + (double) Math.min(r1, r2)) / 2.0;
} else {
return Math.min(r1, r2);
}
} else if (l1 > r2) {
right = mid1 - 1; // Move left
} else {
left = mid1 + 1; // Move right
}
}
// When 'left' crosses 'right', handle the case where nums1 might be empty
int l1 = (left > 0 && left <= nums1.length) ? nums1[left - 1] : Integer.MIN_VALUE;
int l2 = (half - left - 1 >= 0) ? nums2[half - left - 1] : Integer.MIN_VALUE;
int r1 = (left < nums1.length) ? nums1[left] : Integer.MAX_VALUE;
int r2 = (half - left < nums2.length) ? nums2[half - left] : Integer.MAX_VALUE;
if (totalLength % 2 == 0) {
return ((double) Math.max(l1, l2) + (double) Math.min(r1, r2)) / 2.0;
} else {
return Math.min(r1, r2);
}
}
}