LeetCode：Median of Two Sorted Arrays

悠悠 2022-07-12 07:43 125阅读 0赞

第四题是找两个已经排序的数组的中位数，其实就是寻找两个排序数组的第k个数。寻找第k个数就需要把k均分到两个数组，可以用到结论如果a\[k/2-1\]小雨b\[k/2-1\]，那么a\[0\]-a\[k/2-1\]必定存在于第k小的有序数列中。

解题思路如下，还是非常经典的。

*  保持前一个数组A最短， 后一个数组B较长
 *  平分k， 一半在数组A，一半在数组B，如果A的长度不够长，那么pa = min(k/2, len(A)) pb = k-pa
 *  如果A\[pa-1\] < B\[pb-1\]，那么第k个数组肯定不会出现在pa之前的A中，将A的pa之前的序列砍掉，B也同理，递归进行。

**边界条件**：

*  m==0，A已经用完，直接返回B\[k-1\]
 *  k==1，找到第一个数，返回min(A\[0\], B\[0\])
 *  A\[pa - 1\] == B\[pb - 1\]， A\[pa - 1\]和B\[pb - 1\]任意一个就是要找的数。

C++代码

#include <cstdio>
        #include <vector>
        #include <algorithm>
    
        using std::vector;
    
        class Solution {
        public:
            double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
                int n1 = nums1.size();
                int n2 = nums2.size();
                int count = n1 + n2;
                if (count & 0x01) {
                    return findKth(nums1, 0, n1, nums2, 0, n2, count/2 + 1);
                } else {
                    return (findKth(nums1, 0, n1, nums2, 0, n2, count/2)
                        + findKth(nums1, 0, n1, nums2, 0, n2, count/2 + 1)) / 2.0;
                }
            }
        private:
            double findKth(vector<int>& nums1, int s1, int e1,
                    vector<int>& nums2, int s2, int e2, int k) {
                int m = e1 - s1;
                int n = e2 - s2;
                if (m > n) {
                    return findKth(nums2, s2, e2, nums1, s1, e1, k);
                }
                if (m == 0) {
                    return nums2[s2 + k - 1];
                }
                if (k == 1) {
                    return std::min(nums1[s1], nums2[s2]);
                }
                int pa = std::min(k/2, m);
                int pb = k - pa;
                if (nums1[s1 + pa - 1] < nums2[s2 + pb - 1]) {
                    return findKth(nums1, s1 + pa, e1, nums2, s2, e2, k - pa);
                } else if (nums1[s1 + pa -1] > nums2[s2 + pb - 1]) {
                    return findKth(nums1, s1, e1, nums2, s2 + pb, e2, k - pb);
                } else {
                    return nums1[s1 + pa - 1];
                }
            }
        };
    
        int main()
        {
            Solution s;
            vector<int> v1, v2;
            v1.clear();
            v2.clear();
    
            v1.push_back(2);
            // v1.push_back(3);
            // v1.push_back(5);
            // v1.push_back(7);
            // v1.push_back(9);
    
            // v2.push_back(2);
            // v2.push_back(4);
            // v2.push_back(6);
            // v2.push_back(8);
            // v2.push_back(10);
    
            double median = s.findMedianSortedArrays(v1, v2);
    
            printf("median:%.2f\", median); return 0; }

python代码

#! /usr/bin/env python
        # -*- coding:utf8 -*-
    
        class Solution(object):
    
            def findKth(self, nums1, nums2, k):
                m = len(nums1)
                n = len(nums2)
                if m > n:
                    return self.findKth(nums2, nums1, k)
                if m == 0:
                    return nums2[k - 1]
                if k == 1:
                    return min(nums1[0], nums2[0])
                p1 = min(k/2, m)
                p2 = k - p1
                if nums1[p1 - 1] < nums2[p2 - 1]:
                    return self.findKth(nums1[p1:m], nums2, k - p1)
                elif nums2[p2 - 1] < nums1[p1 - 1]:
                    return self.findKth(nums1, nums2[p2:n], k - p2)
                else:
                    return nums1[p1 - 1]
    
            def findMedianSortedArrays(self, nums1, nums2):
                """ :type nums1: List[int] :type nums2: List[int] :rtype: float """
                count = len(nums1) + len(nums2)
                if count & 0x1:
                    return self.findKth(nums1, nums2, count/2 + 1)
                else:
                    return (self.findKth(nums1, nums2, count/2) + self.findKth(nums1, nums2, count/2 + 1))*1.0/2
    
        if __name__ == "__main__":
            s = Solution()
            print s.findMedianSortedArrays([2], [])
            print s.findMedianSortedArrays([], [2])
            print s.findMedianSortedArrays([1, 3, 5, 7], [2, 4, 6, 8, 10])
            print s.findMedianSortedArrays([1, 3, 5, 7, 9], [2, 4, 6, 8, 10])

时间复杂度，整个算法利用了二分查找的思想，二分查找的复杂度为log(n)，序列长度为m+n，所以整个时间复杂度是log(m+n)