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

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

• https://leetcode.com/problems/median-of-two-sorted-arrays/
• https://leetcode.cn/problems/median-of-two-sorted-arrays

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

• 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));
    }
}

要不赞赏一下?

微信

支付宝

PayPal

Bitcoin