接外包,有相关需求的可以联系我:Telegram | Email

寻找两个正序数组的中位数

该文章创建(更新)于11/28/2022,请注意文章的时效性!

Description

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

算法的时间复杂度应该为 O(log (m+n)) 。

Solution

目前是用的合并后排序再找中间值,感觉还有最优解暂时没想出来。

完整代码

  • python
"""
median-of-two-sorted-arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/
"""
import time
from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # TODO: 【优化】 感觉最佳的算法是先计算出中间值的index,通过双指针去拼接就可以直接返回结果,减少一半的计算量
        nums = nums1 + nums2
        nums.sort()

        n = len(nums)
        if n % 2 == 0:
            return (nums[n // 2 - 1] + nums[n // 2]) / 2
        else:
            return nums[n // 2]


if __name__ == '__main__':
    nums1 = [1, 3]
    nums2 = [2]
    S = Solution()
    start_time = time.perf_counter()
    print(S.findMedianSortedArrays(nums1, nums2))
    end_time = time.perf_counter()
    print("time:{}".format(end_time - start_time))
  • java
import java.util.Arrays;

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];
        /*
        TODO: 手动通过双指针去拼接在临界值比较难以处理
        TODO: 【优化】 感觉最佳的算法是先计算出中间值的index,通过双指针去拼接就可以直接返回结果,减少一般的计算量
        int i = 0, j = 0, k = 0;
        System.out.println("nums1.length: " + nums1.length);
        System.out.println("nums2.length: " + nums2.length);
        while(i < nums1.length && j < nums2.length && k < nums.length) {
            System.out.println("i: " + i + "\tj: " + j + "\tk: " + k);
            System.out.println("nums1[i]: " + nums1[i] + "\tnums2[j]: " + nums2[j] + "\tnums[k]: " + nums[k]);
            if (nums1[i] <= nums2[j]) {  // TODO: 一个数组先到达边界值且边界值是小于另一个数组后续的熟知如何处理?
                nums[k] = nums1[i];
                if (i < nums1.length - 1) {
                    i++;
                }
            } else {
                nums[k] = nums2[j];
                if (j < nums2.length - 1) {
                    j++;
                }
            }
            k += 1;
            System.out.println("nums: " + Arrays.toString(nums));
        }
        System.out.println("i: " + i + "\tj: " + j + "\tk: " + k);
        */
        int index = 0;
        for (int i : nums1) {
            nums[index] = i;
            index += 1;
        }

        for (int j: nums2){
            nums[index] = j;
            index += 1;
        }

        System.out.println("nums:\t" + Arrays.toString(nums));
        Arrays.sort(nums);
        System.out.println("nums:\t" + Arrays.toString(nums));


        if (nums.length % 2 == 0) {
            return (nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2.0;
        } else {
            return nums[nums.length / 2];
        }
    }
}

public class FindMedianSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        Solution solution = new Solution();
        System.out.println(solution.findMedianSortedArrays(nums1, nums2));
    }
}


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/11/28/median-of-two-sorted-arrays/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码