This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
preface
The fourth buckle is as follows:
A, thinking
The following two information can be learned from the question
- Input: two arrays (positive order)
- Output: median
So the easiest way to think about it is to combine the two arrays into one array and take the median
Second, the implementation
Code implementation
The complete code is shown below:
/** * merge * time complexity O(m+n) */
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] arr = new int[nums1.length + nums2.length];
int index1 = 0;
int index2 = 0;
for (int i=0; i<arr.length; i++) {
// Compare two arrays of elements, the smallest of which goes in
if (index2 == nums2.length || (index1 < nums1.length && nums1[index1] <= nums2[index2])) {
arr[i] = nums1[index1];
index1 ++;
} else{ arr[i] = nums2[index2]; index2++; }}// Get the median
if (arr.length % 2= =0) {
return ((double) arr[arr.length/2] + (double) arr[arr.length/2 - 1) /2;
} else {
return arr[arr.length/2]; }}Copy the code
The test code
The test code is shown below:
public static void main(String[] args) {
Number4 n = new Number4();
int[] nums1 = {2.3};
int[] nums2 = {1.4.5.7};
double ret = n.findMedianSortedArrays(nums2, nums1);
System.out.println("ret:" + ret);
}
Copy the code
Third, summary
Today is the fourth buckle ~ this series will update the buckle 1-10 questions, continuous update for 10 days! Dig gold coin, I come 😁