题意整理
- 给定两个升序的数列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小的数。但是如果两个数组的长度比较大,这种做法的时间复杂度会相当高(级别),违背了题目的初衷。
图解展示:
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次,所以时间复杂度是。
- 空间复杂度:需要额外常数级别的空间,所以空间复杂度为。
方法二(小顶堆)
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次,总共最多执行次操作,每次操作时间复杂度约为,所以时间复杂度是。
- 空间复杂度:最坏情况下,需要额外大小为K的小顶堆,所以空间复杂度为。