LEETCODE4

LEETCODE4

题目描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

JAVA代码

//手写体
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums3 = new int[2000];
        int m = nums1.length;
        int n = nums2.length;
        for (int i = 0; i < m; i++) {
            nums3[i] = nums1[i];
        }
        for (int i = 0; i < n; i++) {
            nums3[m + i] = nums2[i];
        }
        int temp = 0;
        int k = 0;
        for (int i = 0; i < m + n; i++) {
            k = i;
            for (int j = i + 1; j < m + n; j++) {
                if (nums3[k] > nums3[j]) {
                    k = j;
                }
            }
            temp = nums3[k];
            nums3[k] = nums3[i];
            nums3[i] = temp;
        }
        double Median;
        k = (m + n) / 2;
        if ((m + n) % 2 == 0) {
            Median = nums3[k] + nums3[k - 1];
            Median = Median / 2;
        } else {
            Median = nums3[k];
        }
        return Median;
    }
}