题意整理

  • 给定两个升序的数列arr1、arr2,和一个整数target。
  • 找出两个数列中第K小的值,其中K等于target。

方法一(归并)

1.解题思路

  • 执行K次循环,每次将较小的值赋值给res。
  • 新建两个变量id1、id2,id1是arr1数组游标,id2是arr2数组游标。如果id1和id2都没有到末尾,将两者指向的值中较小的赋值给res,并后移游标。
  • 如果id1到达末尾,则继续将arr2数组的值赋值给res。否则,将arr1数组的值赋值给res。

有一种简单的做法是直接将两个数组的值存储到一个新数组中,然后对新数组进行排序,索引为K-1的值即是第K小的数。但是如果两个数组的长度比较大,这种做法的时间复杂度会相当高(O((m+n)log2(m+n))O((m+n)*log_2{(m+n)})级别),违背了题目的初衷。

图解展示: alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findKthNum (int[] arr1, int[] arr2, int target) {
        int m=arr1.length;
        int n=arr2.length;
        //用于记录结果
        int res=0;
        //id1是arr1数组游标,id2是arr2数组游标
        int id1=0,id2=0;
        
        //循环K次,每次将较小的值赋值给res,最后res一定是第K小的数
        while(target-->0){
            //如果id1和id2都没有到末尾
            if(id1<m&&id2<n){
                //将两者中较小的赋值给res,并后移游标
                if(arr1[id1]<arr2[id2]){
                    res=arr1[id1++];
                }
                else{
                    res=arr2[id2++];
                }
            }
            //如果id1到达末尾,则继续将arr2数组的值赋值给res
            else if(id1==m){
                res=arr2[id2++];
            }
            //否则,将arr1数组的值赋值给res
            else{
                res=arr1[id1++];
            }
        }
        return res;
    }
}

3.复杂度分析

  • 时间复杂度:需要给res赋值K次,循环总共执行K次,所以时间复杂度是O(K)O(K)
  • 空间复杂度:需要额外常数级别的空间,所以空间复杂度为O(1)O(1)

方法二(小顶堆)

1.解题思路

  • 首先新建小顶堆,将arr1数组中可能第K小的所有数字加到堆中(如果K小于m,则前K个数可能第K小,直接将前K个数加入堆中。如果k大于等于m,则数组中所有元素都可能第K小,全部入堆)。
  • 然后遍历arr2数组,每次将当前元素与堆顶元素比较,将较小的数赋值给res。如果n大于等于K,则循环K次后,res一定是第K小。如果n小于K,则只赋值了n次,继续将堆顶元素赋值给res,直到满足K次。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findKthNum (int[] arr1, int[] arr2, int target) {
        int m=arr1.length;
        int n=arr2.length;
        //新建小顶堆
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        //将arr1中可能第K小的所有数字加到堆中
        for(int i=0;i<Math.min(m,target);i++){
            queue.offer(arr1[i]);
        }
        //记录结果的变量
        int res=0;
        //遍历arr2数字,每次将较小的数赋值给res
        for(int i=0;i<Math.min(n,target);i++){
            if(queue.peek()<=arr2[i]){
                res=queue.poll();
                //arr2[i]可能是前K小的元素,加入堆中
                queue.offer(arr2[i]);
            }
            else{
                res=arr2[i];
            }
        }
        //如果n大于等于K,则res被赋值K次,直接是第K小的数。如果小于K,则不断取出堆中元素,直到等于K
        while(n<target){
            res=queue.poll();
            target--;
        }
        return res;
    }
}

3.复杂度分析

  • 时间复杂度:第一次循环将元素加入小顶堆,最多执行K次,之后的操作,需要给res赋值K次,所以循环会执行K次,总共最多执行2K2*K次操作,每次操作时间复杂度约为O(log2K)O(log_2K),所以时间复杂度是O(Klog2K)O(K*log_2K)
  • 空间复杂度:最坏情况下,需要额外大小为K的小顶堆,所以空间复杂度为O(K)O(K)