题解 | #多数组第 K 小数#

题目的主要信息：

给定两个升序的数列 arr1 和 arr2 ，和一个整数 target ，请你找出两个数列中第 K 小的值。

方法一：

同时遍历两个数组，由于两个数组已经是升序排序的，所以每次我们两数相比取更小的，直到取到第k个数就结束循环。需要注意的是，如果在遍历过程中，有数组提前结束遍历，则在另一个数组中继续。 具体做法：

class Solution {
public:
    int findKthNum(vector<int>& arr1, vector<int>& arr2, int target) {
        int i = 0;//遍历arr1
        int j = 0;//遍历arr2
        int count = 0;
        int res = 0;
        while(i < arr1.size() || j < arr2.size()) {//遍历两个数组
            if (count == target) {//如果找到第target个数则结束循环
                break;
            }
            if (i == arr1.size()) {//arr1遍历完了则在arr2数组中继续
                res = arr2[j++];
            } else if (j == arr2.size()) {//arr2遍历完了则在arr1数组中继续
                res = arr1[i++];
            } else {//两个数组都没有遍历完
                if (arr1[i] > arr2[j]) {//取其更小的数
                    res = arr2[j++];
                } else {
                    res = arr1[i++];
                }
            }
             
            count++;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，while循环遍历两个数组，n为两个数组中较大的长度。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

先合并两个数组，然后再对合并后的数组排序，最后直接返回第target个数。

具体做法：

class Solution {
public:
    int findKthNum(vector<int>& arr1, vector<int>& arr2, int target) {
        for(int i=0;i<arr2.size();i++){//合并
            arr1.push_back(arr2[i]);
        }
        sort(arr1.begin(),arr1.end());//排序
        return arr1[target-1];//返回第target个数
    }
};

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，sort函数的时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$，n为两个数组长度之和。
• 空间复杂度：$O(n)O(n)$，合并数组后，arr1的大小为n，n为两个数组长度之和。