leetcode 刷题（数组篇）4题寻找两个正序数组的中位数（二分查找）

题目描述

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

示例 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

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

LeetCode

解法

方法一暴力搜索

直接合并两个数组，时间复杂度为O(n+m)，空间复杂度为O(1)

class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int m = nums1.length;

        int n = nums2.length;

        int len = m + n;

        int[] mid = new int[2];

        // 定义两个指针

        int i = 0, j = 0, k = 0;

        while (i + j <= (len >> 1)) {

            k = i + j == (len >> 1) ? 1 : 0;

            if (i <= m - 1 && j <= n - 1) {

                mid[k] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];

            }

            else if (i == m) {

                mid[k] = nums2[j++];

            }

            else {

                mid[k] = nums1[i++];

            }

        }

        if ((len & 1) == 1) {

            return mid[1];

        }

        else {

            return (mid[0] + mid[1])/2.0;

        }

    }

}

Accepted

2094/2094 cases passed (2 ms)

Your runtime beats 100 % of java submissions

Your memory usage beats 32.02 % of java submissions (39.8 MB)

方法二二分查找

用二分查找找到第k小的数字，时间复杂度为O(log(m+n))，空间复杂度为O(1)

class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int m = nums1.length;

        int n = nums2.length;

        int len = m + n;

        if ((len & 1) == 1) {

            int midIdx = len >> 1;

            double mid = getKthElement(nums1, nums2, midIdx + 1);

            return mid;

        }

        else {

            int midIdx1 = len >> 1 - 1;

            int midIdx2 = len >> 1;

            double mid = (getKthElement(nums1, nums2, midIdx1 + 1) + getKthElement(nums1, nums2, midIdx2 + 1))/ 2.0;

            return mid;

        }

    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {

        int m = nums1.length, n = nums2.length;

        int offset1 = 0, offset2 = 0;

        while (true) {

            // 边界情况，返回终值

            // 1.有一个数组遍历完

            if (offset1 == m){

                return nums2[offset2 + k - 1];

            }

            if (offset2 == n){

                return nums1[offset1 + k - 1];

            }

            // 2.k值为1

            if (k == 1) {

                return Math.min(nums1[offset1], nums2[offset2]);

            }

            // 正常情况

            // 判断索引, 是否会出界

            int mid = k >> 1;

            int idx1 = Math.min(offset1 + mid, m) - 1;

            int idx2 = Math.min(offset2 + mid, n) - 1;

            // 判断索引值大小, 更新k值和偏移量

            if (nums1[idx1] <= nums2[idx2]) {

                k -= (idx1 - offset1 + 1); // 正常情况如果不出界，就是减去mid

                offset1 = idx1 + 1;

            }

            else {

                k -= (idx2 - offset2 + 1);

                offset2 = idx2 + 1;

            }

        }

    }

}

巴特西

leetcode 刷题（数组篇）4题寻找两个正序数组的中位数（二分查找）

题目描述

解法

最新文章

热门文章

巴特西

leetcode 刷题（数组篇）4题 寻找两个正序数组的中位数（二分查找）

题目描述

解法

最新文章

热门文章

leetcode 刷题（数组篇）4题寻找两个正序数组的中位数（二分查找）