[LeetCode] 4. Median of Two Sorted Arraysjava

/**4. Median of Two Sorted Arrays * @param nums1 * @param nums2 * @return 两个数字的中数 */ public double findMedianSortedArrays(int[] nums1, int[] nums2) { int []nums = new int[nums1.length + nums2.length]; int i = 0; for (int j = 0; j < nums1.length; j++) { nums[i++] = nums1[j]; } for (int j = 0; j < nums2.length; j++) { nums[i++] = nums2[j]; } Arrays.sort(nums); if (nums.length%2 == 1) { return nums[nums.length/2]; } else { int hlen = nums.length/2; double m = (double)(nums[hlen] + nums[hlen-1])/2; return m; } }

改进：寻找第k大的数

/**4. Median of Two Sorted Arrays * @param nums1 * @param nums2 * @return 两个数字的中数 */ public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1 = nums1.length; int len2 = nums2.length; if ((len1+len2)%2 == 1) {//奇数 return findNum((len1+len2)/2, nums1, nums2); } else { return (double)(findNum((len1+len2)/2, nums1, nums2)+findNum((len1+len2)/2+1, nums1, nums2))/2; } } public int findNum(int k, int[] nums1, int[] nums2) { int x = 0, y = 0; int xlen = nums1.length; int ylen = nums2.length; for (int i=1; i<=k; i++) { if (x < xlen && y < ylen) { if (nums1[x] < nums2[y]) { if (i == k) { return nums1[x]; } x++; } else { if (i == k) { return nums2[y]; } y++; } } else if (x >= xlen) { if (i == k) { return nums2[y]; } y++; } else if (y >= ylen) { if (i == k) { return nums1[x]; } x++; } } return 0; } // beats 86.81%