Leetcode 4. Median of Two Sorted Arrays 题解

最后编辑于: 2016-03-31

我的解

一开始没注意到时间复杂度限制是 $\mathcal{O}(log(m+n))$ ，写了一个 $\mathcal{O}(m+n)$ 的出来。思路很直接，合并两个数组然后求中位数。

44ms

class Solution {
    public:
        void all_in (std::vector<int>& winner, std::vector<int>* merge_nums, int flag)
        {
            for (int i = flag - 1; i < winner.size(); ++i)
                merge_nums->push_back(winner[i]);
        }

        double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
            std::vector<int> merge_nums;
            if(!nums1.size())
                merge_nums = nums2;
            else if (!nums2.size())
                merge_nums = nums1;
            else
            {
                int coin = nums1[0] - nums2[0];
                int defense = coin ? nums1[0]:nums2[0];
                int flag1 = coin ? 1:0;
                int flag2 = coin ? 0:1;
                unsigned int offense = coin ? 2:1;
                while(true)
                {
                    int soldier = (offense == 1)? nums1[flag1++]:nums2[flag2++];
                    if(soldier > defense)
                    {
                        merge_nums.push_back(defense);
                        defense = soldier;
                        bool is_allin = (offense == 1)? (flag2==nums2.size()):(flag1==nums1.size());
                        if(is_allin)
                        {
                            all_in((offense == 1)? nums1:nums2, &merge_nums, (offense == 1)? flag1:flag2);
                            break;
                        }
                        offense = (offense == 1)? 2:1;
                    }
                    else
                    {
                        merge_nums.push_back(soldier);
                        bool is_allin = (offense == 1)? (flag1==nums1.size()):(flag2==nums2.size());
                        if(is_allin)
                        {
                            all_in((offense == 1)? nums2:nums1, &merge_nums, (offense == 1)? flag2:flag1);
                            break;
                        }
                    }
                }
            }
            size_t size = merge_nums.size();
            if (size == 0)
                return (double)0;
            else if(size & 0x1)
                return (double)merge_nums[size/2];
            else
                return (double)(merge_nums[size / 2 - 1] + merge_nums[size / 2]) /2;
        }
};

也可以在merge_nums.size()达到了两个数组元素总个数的一半时就返回，可以降低一定的时间复杂度。

更好的解

一个一个的处理，虽然利用了两个数组有序这一特征，但是步长太小了。将问题转化了求两个数组合并后第k大的数的问题，可以使用二分法将时间复杂度降低到 $\mathcal{O}(log(m+n))$ 。若nums1[k/2-1]比nums2[k/2-1]大，证明nums2[0]到nums[k/2-1]一定在合并后的前k个数中，这样一次就排除了一半k的数。

其实也没快多少，因为此题的中位数要求导致k不会接近于m+n的规模。

40ms

class Solution {
    public:
        int binary_k(std::vector<int>& nums1, size_t flag1, std::vector<int>& nums2, size_t flag2, size_t k)
        {
            if (nums1.size() - flag1 > nums2.size() - flag2)
                return binary_k(nums2, flag2, nums1, flag1, k);
            if (nums1.size() - flag1 == 0)
                return nums2[flag2 + k - 1];
            if (k == 1)
                return std::min(nums1[flag1], nums2[flag2]);

            size_t index_1 = std::min(k/2, nums1.size());
            size_t index_2 = k - index_1;
            if (nums1[flag1 + index_1 - 1] < nums2[flag2 + index_2 - 1])
            {
                return binary_k(nums1, flag1 + index_1, nums2, flag2, k - index_1);
            }
            else if (nums1[flag1 + index_1 - 1] > nums2[flag2 + index_2 - 1])
            {
                return binary_k(nums1, flag1, nums2, flag2 + index_2, k - index_2);
            }
            else
            {
                return nums1[flag1 + index_1 -1];
            }
        }

        double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
            size_t total = nums1.size() + nums2.size();
            size_t flag1 = 0, flag2 = 0;
            if (total & 0x1)
            {
                return (double)binary_k(nums1, flag1, nums2, flag2, total/2 + 1);
            }
            else
            {
                return (double)(binary_k(nums1, flag1, nums2, flag2, total/2) + binary_k(nums1, flag1, nums2, flag2, total/2 + 1)) / 2;
            }
        }
};

启发

分治法、二分法、递归。。。永远的硬伤。这道题加上复杂度限制确实可作为 Hard级别。