Leetcode – Finds the median of two positive ordinal groups
Leetcode-cn.com/problems/me…
Given two positively ordered (from small to large) arrays of size m and n, nums1 and nums2. Please find and return the median of the two positive ordinal groups.
Advanced: Can you design a time complexity O(log (m+n)) algorithm to solve this problem?
Example 1:
Input: nums1 = [1,3], nums2 = [2] output: 2.00000 explanation: merge array = [1,2,3], median 2
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5
Example 3:
Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000 example 4:
Input: nums1 = [], nums2 = [1] Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = [] Output: 2.00000
Tip:
nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], Nums2 [I] <= 106 Pass count 268,312 submit count 691,163
The code is a little long, the idea is very simple; If nums1 is null, then find the median of the second array (nums2). If nums2 is null, then find the median of the first array (nums2). If nums1 is null, then find the median of the first array (nums2)
Other package. A question of the day; import java.util.Arrays; class Solution { static public double findMedianSortedArrays(int[] nums1, int[] nums2) { if(nums1.length==0) return findMidArrays(nums2); if(nums2.length==0) return findMidArrays(nums1); int[] hebing = hebing(nums1, nums2); return findMidArrays(hebing); } private static int[] hebing(int[] nums1, int[] nums2){ int len1 = nums1.length; int len2 = nums2.length; int[] newIntArray = new int[len1+len2]; int newIndex = 0; int i = 0; int j = 0; while (len1! =0 && len2! =0){ if(nums1[i]>nums2[j]){ newIntArray[newIndex]=nums2[j]; len2--; j++; }else{ newIntArray[newIndex]=nums1[i]; len1--; i++; } newIndex++; } if(len1! =0){ for (int k = i; k < nums1.length; k++) { newIntArray[newIndex]=nums1[k]; newIndex++; } } if(len2! =0){ for (int k = j; k < nums2.length; k++) { newIntArray[newIndex]=nums2[k]; newIndex++; } } return newIntArray; } private static double findMidArrays(int[] nums) { if(nums.length==2){ return nums[0]+nums[1]==0? Zero: (nums [0] + nums [1]) / 2.0; } double midNumber = 0; int numsLen = nums.length; if(numsLen%2==0){ int len = numsLen / 2; MidNumber = (nums[len] + nums[len-1]) / 2.0; }else{ numsLen = (nums.length/2)+1; midNumber = nums[numsLen-1]; } return midNumber; } public static void main(String[] args) {system.out.println (findMedianSortedArrays(new int[]{1,2,3,4,5,6},new int[]{})); System. The out. Println (findMedianSortedArrays (new int [] {1, 3}, new int [] {2})); }}Copy the code