ARTS-Week-3

第三周

Alogrithm

题目—Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

第一次做hard等级的题目，思路是找到中点则需要num1和num2中点左右两边数的个数分别相加数量相等，同时中点值一致。也就是由较短那个数列主导分隔位置的移动。由于中间间隔要求两边分隔出的元素数量相等，且分隔两边正好在两有序数列的中点上，故总结出如下要求：

设数组分隔方式为：

      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

需要要求如下：

• m < n
• j = (m+n+1)/2 - i
• max(A[i-1], B[j-1]) < min(A[i], B[j])

查找到这条分割线后，即可求得分隔结果：

• 如m+n为偶数：(max(A[i-1], B[j-1]) + min(A[i], B[j]))/2
• 如m+n为奇数：min(A[i-1], B[j-1])

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    int findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if (i >= nums1.size()) return nums2[j + k - 1];
        if (j >= nums2.size()) return nums1[i + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int midVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX;
        int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }
};

Review

SSL session flow
ssl的流程

Tip

Ldd的使用：
一天一个命令 - ldd

Share

信息太杂乱了，可以归拢下消息源。比如启用Reedly一类的RSS阅读器，https://feedx.net。