4. Median of Two Sorted Arrays | U+2647's blog

• 刷题仓库地址
• 4. Median of Two Sorted Arrays
• 10. Regular Expression Matching
• 23. Merge k Sorted Lists
• 25. Reverse Nodes in k-Group
• 30. Substring with Concatenation of All Words
• 32. Longest Valid Parentheses
• 37. Sudoku Solver

---

Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Translation

给定两个有序数组nums1和nums2大小分别为m和n。

找到这两个数组的中位数。整体运行时间复杂度应为O（log（m + n））。

Ideas

归并排序，二路归并，归并到一半就出结果了。注意结果是小数。

Note

注意测试数据:

num1 = [],num2 = [1,2,3]
num1 = [1,2,3],num2 = [1]
num1 = [1],num2 = [1,2,3]

Accept Code

public class MedianTwoArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int T = nums1.length + nums2.length;
        double result;
        List<Integer> nums3 = new ArrayList<>(T);
        int i1 = 0;
        int i2 = 0;
        int i3 = 0;

        int num1;
        int num2;
        while (i3 <= T / 2) {
            num1 = (i1 == nums1.length) ? Integer.MAX_VALUE : nums1[i1];
            num2 = (i2 == nums2.length) ? Integer.MAX_VALUE : nums2[i2];
            if (num1 < num2) {
                nums3.add(num1);
                i1++;
            } else {
                nums3.add(num2);
                i2++;
            }
            i3++;
        }

        int temp;
        if (T % 2 != 0) {
            temp = nums3.get(i3 - 1);
            result = (temp + temp) / 2.0;
        } else {
            temp = nums3.get(i3 - 2) + nums3.get(i3 - 1);
            result = temp / 2.0;
        }
        return result;
    }
}

转载请注明出处
本文链接：https://zdran.com/20180327.html