字节ailab后端实习凉经

上次面字节是半年前，当时一面挂，上周五被hr捞出来了

面试官迟到半小时（提前给我打了电话告知会晚点）

没有自我介绍，上来聊了点项目，面试官兴趣不大，开始做题

第1题：

2个有序数组的第K小元素

题目描述

两个已经排好序的数组，找出两个数组合并后的第K小的数。如两个数组[123456][6789 10 11 12]，K=8输出:7

只会暴力不会优化，给我换了第二题

第2题：力扣165比较版本号

第二题写出来了

第一题题解

int get_kth_smallest(vector<int> nums1, vector<int> nums2, int k) {
        // 保证nums1.size() <= nums2.size()，方便分析
        if (nums1.size() > nums2.size()) return get_kth_smallest(nums2, nums1, k);
        if (nums1.empty()) return nums2[k-1];
        if (1 == k) return nums1[0] < nums2[0]? nums1[0]:nums2[0];
    
        // 在nums1和nums2中分别取第k/2个数字。当然，如果k/2已经超出数组边界，我们只取数组最后的那个数字。
        int k1 = min(static_cast<int>(nums1.size()), k/2);
        int k2 = min(static_cast<int>(nums2.size()), k/2);
    
        if (nums1[k1-1] < nums2[k2-1]) {
            // 如果nums1[k1-1] < nums2[k2-1]，说明nums1[k1-1]小于我们要找的第k小的数字。
            nums1.erase(nums1.begin(), nums1.begin()+k1);
            return get_kth_smallest(nums1, nums2, k-k1);
        } else {
            // 如果nums1[k1-1] > nums2[k2-1]，说明nums2[k2-1]小于我们要找的第k小的数字。
            // 如果nums1[k1-1] == nums2[k2-1]，说明nums2[k2-1]小于或等于我们要找的第k小的数字。即使nums2[k2-1]等于我们要找的第k小的数字，我们依然可以删掉它，因为还有nums1[k1-1]和它相等呢！
            nums2.erase(nums2.begin(), nums2.begin()+k2);
            return get_kth_smallest(nums1, nums2, k-k2);
        }
    }

看不懂的看下面的思路

让我们假设k是4：
nums1： [a1, a2, a3, ...]
nums2： [b1, b2, b3, ...]
如果a2<b2，那么a2肯定可以删除。因为有可能比a2小的数字只有：

a1。它肯定比a2小，因为数组已排序。
b1。它有可能比a2小。
因此，a2最多只能是第3小的数字，肯定比我们要找的第4数字要小！从而a2，以及比a2还小的a1，都可以删除。

删除这两个数字以后，问题变成了:
nums1： [a3, ...]
nums2： [b1, b2, b3, ...]
从以上两个已排序数组中找出第2小的数字。（k已经变了，因为我们已经删除了两个比我们要找的那个数字还小的数字。）

同理，我们可以删除a3和b1中较小的那个数字，然后问题变成从剩余数字中找到第1小的数字。这个问题不就简单了吗？

推广以上方法，我们可以写出上述的get_kth_smallest函数：