52XUE Logo

好好学习,天天向上



LeetCode刷题(4):两数之和

 题目:

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

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

准备:

       这里我们需要明白“中位数”是什么,顾名思义,对于一组有序数组来说,中位数$min就是一组数的中间位置,它比左边的数大,比右边的数小,且左右两边数的个数相等。对于偶数个的有序数组来说,中位数会有两个。对于奇数个的有序数组来说,中位数只会有1个。

题解1:

       由于都是有序数组,我们考虑的第一种解法就是合并两个数组。先拿数组$nums1逐个与数组$nums2比较,如果比数组2小,则放入合并的数组$nums中,自己的脚标往后移动1位;如果数组1的值更大,那么数组2的值都可能比数组1这个值小,此时数组2的脚标要往后移1位,逐个与数组1比较,如此循环往复,则数组所有元素都进行了比较,合成全新的有序数组$nums。时间复杂度O(m+n),空间复杂度O(m+n)。

function findMedianSortedArrays($nums1, $nums2) {
    $count = $i = $j = 0;
    $count1 = count($nums1);
    $count2 = count($nums2);
    $nums = [];
    while ($count < ($count1+$count2)) {

        // 如果数组1已经比完
        if ($i == $count1) {
            while ($j < $count2) {
                $nums[$count++] = $nums2[$j++];
            }

            break;
        }

        // 如果数组2已经比完
        if ($j == $count2) {
            while ($i < $count1) {
                $nums[$count++] = $nums1[$i++];
            }

            break;
        }

        // 由于两个都是有序数组,数组1逐个与数组2的值比较
        if ($nums1[$i] < $nums2[$j]) {
            $nums[$count++] = $nums1[$i++];
        }else{
            $nums[$count++] = $nums2[$j++];
        }
    }

    // 1 2 3 5 6 9
    if ($count%2 == 0) {
        return ($nums[$count/2-1] + $nums[$count/2])/2;
    }else{
        return $nums[($count+1)/2-1];
    }
}

执行结果:通过

执行用时 : 44 ms, 在所有 php 提交中击败了55.09%的用户

内存消耗 :15.5 MB, 在所有 php 提交中击败了5.12%的用户


结论:

        可见时间和空间复杂度都还有可以优化的地方。


作者  :  超人会飞吗

天上地久有时尽,此恨绵绵无绝期。




about me

剪一束月光

秋风清,秋月明。
落叶聚还散,
寒鸦栖复惊。
相思相见知何日,
此时此夜难为情。

联系站长

热门标签