2022-10-9 周记 0x001

分析：
    nums1: xxx X xxx
    nums2: yyy Y yyyyy
    在两个数组里找第k/2个数
    当X<Y时，说明第k个数一定不在数组nums1[start,k/2]里，因为nums1[start,k/2]有个k/2个数都小于Y，加上nums2[start,k/2 - 1]的个数才有k-1个数。
    同理当Y<X时
细节：
    k分配不一定均匀,nums1数组元数可能不够k/2个
    写个函数findKth(nums1, nums2, i, j, k)
    确保nums1里元数个数 < nums2里元数个数
    当左边数组遍历完了(i==nums1.size()) 返回nums2中的第k个数
    当k==1时返回两个数组里的最小值

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size() + nums2.size();
        if (n % 2 == 0) {
            return (findKth(nums1, nums2, 0, 0, n / 2)
                    + findKth(nums1, nums2, 0, 0, n / 2 + 1)) / 2.0;
        } else {
            return findKth(nums1, nums2, 0, 0, n / 2 + 1);
        }
    }
 
    int findKth(vector<int> &nums1, vector<int> &nums2, int i, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) {
            return findKth(nums2, nums1, j, i, k);
        }
        if (i == nums1.size()) return nums2[j + k - 1];
        if (k == 1) return std::min(nums1[i], nums2[j]);
        int k1 = std::min((int)nums1.size() - i, k / 2);
        int k2 = k - k1;
        if (nums1[i + k1 - 1] < nums2[j + k2 - 1]) {
            return findKth(nums1, nums2, i + k1, j, k2);
        } else {
            return findKth(nums1, nums2, i, j + k2, k1);
        }
    }
};

go env -w GO111MODULE=on
go env -w GOPROXY=https://goproxy.io,direct