Description of topic
Given two positively ordered (from small to large) arrays nums1 and nums2 of sizes m and n respectively. Please find and return the median of these two ordinal arrays.
The time complexity of the algorithm should be O(log (m + n)) .
Link to the topic
Find the median of two ordinal arrays
Test case
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] , median 2
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: Combined array = [1,2,3,4] , median (2 + 3) / 2 = 2.5
Solution 1: Combine arrays
Thoughts
Merge the two arrays directly, and find the median according to the parity of the number of elements in the merged array
Problem solving code
class Solution {<!-- -->
public double findMedianSortedArrays(int[] nums1, int[] nums2) {<!-- -->
// merged array
int[] sum = new int[nums1. length + nums2. length];
//i, j are the array subscripts of nums1 and nums2 respectively, and n1, n2 correspond to the values of the array subscripts
//k represents the array subscript of the merged array
int i=0, j=0, k=0, n1, n2;
while(i<nums1.length || j<nums2.length){<!-- -->
//Note that the smaller data is put into the sum array, so if an array element is empty, it should be the maximum value
n1 = i<nums1.length ? nums1[i] : (int)Math.pow(10,6);
n2 = j<nums2.length ? nums2[j] : (int)Math.pow(10,6);
if(n1 < n2){<!-- -->
sum[k] = n1;
i + + ;
k++;
}else{<!-- -->
sum[k] = n2;
j + + ;
k++;
}
}
//double type! avoid division with remainder
double result;
if(sum.length%2 == 0){<!-- -->
// Pay attention to cast to doble type
result = ((double)sum[sum. length/2] + sum[sum. length/2-1])/2;
}else{<!-- -->
result = sum[sum. length/2];
}
return result;
}
}
There is a problem
Simple merging arrays, the time complexity is O(m + n), which does not meet the requirements of O(log(m + n)) in the title
Solution 2
Remove elements that cannot be the median at each judgment
Thoughts
- solve by recursion
- Find the kth largest element in the array nums1 and nums2, you can find the k/2th element of the two arrays, and then judge the size of the two elements
- If the k/2th element of nums1 is small, it means that the first k/2 elements in the array nums1 must not meet the requirements! Then the problem is transformed into finding (nums1-first k/2 elements) and nums2’s (k-number of elements deleted by nums1) large elements
- Note that the comparison here is not necessarily the k/2th element in nums1 and nums2, you need to consider whether there are k/2 elements in the two arrays, if not, then judge the last element of the array
- Conditions for recursive exit
(1) There is an array with a length of 0, and the kth element of another array is returned
(2) k=1, returns the minimum value of the first element in the current two arrays
Note: The order of these two conditions cannot be reversed! Avoid array out of bounds - Tip: The sum of the number of elements in the two arrays is an odd or even number, which affects the solution to the median, and it is converted into a situation for easy solution: both are averaged
Problem solving code
class Solution {<!-- -->
public double findMedianSortedArrays(int[] nums1, int[] nums2) {<!-- -->
//Record the length of the two arrays
int nums1Length = nums1. length;
int nums2Length = nums2. length;
//Merge odd or even array numbers, and finally find the average value of the left and right numbers
//The number of elements in the merged array has an odd number: 12345, left=right=3 [The number of elements in the array to be merged is 2 and 3 respectively]
//The number of elements in the merged array has an even number: 123456, left=3, right=4 [The number of elements in the array to be merged is 3 3 respectively]
int left = (nums1Length + nums2Length + 1) / 2;
int right = (nums1Length + nums2Length + 2) / 2;//default rounded down
//The final result is the average value of the right and left array elements
return (findKth(nums1, 0, nums1Length-1, nums2, 0, nums2Length-1, left) +
findKth(nums1, 0, nums1Length-1, nums2, 0, nums2Length-1, right))/2;
}
/**
Find the kth largest element in the two arrays.
If the k/2th largest element in num1 <the k/2th largest element in num2, it means that the first k/2 elements in num1 do not meet the requirements
The topic becomes (remove num1 of the first k/2 elements in num1) and the (k/2-number of removed elements) element of len2
Exit recursion condition: (1) k=1, compare the size of the start value of the two arrays, and return the smallest one (2) if the element in one array is empty, directly return the kth element in the other array
Parameters to be passed in: two arrays, the start and end of the two arrays (the comparison is the number between the array subscripts in the two arrays from start to end), k (need to find the kth element)
*/
public double findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k){<!-- -->
int length1 = end1 - start1 + 1;//The array length of num1
int length2 = end2 - start2 + 1;//num2 array length
//If the lengths of the two arrays are different, nums1 is always an array with a smaller length (easy to write exit recursion conditions)
if(length1 > length2){<!-- -->
return findKth(nums2, start2, end2, nums1, start1, end1, k);
}
//The condition for exiting recursion, pay attention to the order of 1 and 2! avoid crossing the line
//1. One array is empty, that is, find the kth element of another array
if(length1 == 0){<!-- -->
// Return the kth element in num2 after the change (currently the subscript of nums2 starts from start2)
return nums2[start2 + k - 1];
}
//2. k=1, that is, find the first smallest value in the two arrays
if(k == 1){<!-- -->
//Returns which of the two arrays' starting subscripts corresponds to the smaller element
return Math.min(nums1[start1], nums2[start2]);
}
//Loop recursion, if the k/2th element of one array num1 is smaller than another array num2, then the first k/2 elements in num1 are not the minimum value
//You can remove the first k/2 elements in num1 (modify the start of num1), and then find the modified num1 and the initial num2's (k-number of elements to delete num1) element
//Note that judging the length of the array and the size of k/2, a smaller value should be taken to avoid crossing the boundary
int i = Math.min(start1 + length1 -1, start1 + k/2 -1);//Record the array subscript of num1 elements to be judged
int j = Math.min(start2 + length2 -1, start2 + k/2 -1);//Record the array subscript of num2 elements to be judged
//-1 is because the array subscript starts from 0
//The first j elements of num2 are deleted
if(nums1[i] > nums2[j]){<!-- -->
// A total of j-start2 + 1 elements have been deleted
return findKth(nums1, start1, end1, nums2, j + 1, end2, k-(j - start2 + 1));
}else{<!-- -->
return findKth(nums1, i + 1, end1, nums2, start2, end2, k-(i - start1 + 1));
}
}
}
Java while learning
Index
Find the exponent Math.pow
double pow(double base, double exponent) //The returned result is in double form, pay attention to format conversion (int)Math.pow(10,6)
Division operation
In the division operation, two integers are divided. If you want to get double type data, you need to convert one of the divisors to double type first, otherwise you will always get integer type data.
eg: (3 + 2)/2=2, ((double)3 + 2)/2=2.5