5.Kth Largest Element:点击打开链接
例如:[9,3,2,4,8],k=3,Output:4,也就是第3rd大的是4,[2,3,4,8,9]
思路:1. 用当前数组中间的数作为pivot标杆,用O(n)的时间使得大于pivot的数都在左边部分,小于pivot的数都在右边部分
2. 然后就要进行一轮判断,如果判断出k会在左边部分,右边部分就不用再递归了,同理,如果k会在右边也一样处理。
3. 最后跳出while循环有两种情况,但要分成三种情况判断
如果i<j是最后一次循环,i++使得i向前走一步,j--使得j向前走一步,结果i>j跳出循环,此时的相对位置[...j,i...]
如果i=j是最后一次循环,i++使得i向前走一步,j--使得j向前走一步,结果i>j跳出循环,此时的相对位置[...j,pivot,i...]
注意:1. 思路就是T(n)=O(n)+T(n/2),所以时间复杂度还是O(n)
但如果用先排序再输出最大值的方法,时间复杂度最好也是O(nlogn)(快排,归并排序),这就是这题为啥要这么折腾一大圈的原因
2. 和follow up是一样的,两种解法都可以直接用在其上,606.Kth Largest Element II: 点击打开链接
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) {
if(nums==null || nums.length==0 || k<=0){
return -1;
}
return quickSelect(nums,0,nums.length-1,k);
}
private int quickSelect(int[] nums,int start,int end,int k){
if(nums[start]==nums[end]){ //例如数组只有一个数[1],k=1
return nums[start];
}
int i=start;
int j=end;
int pivot=nums[(i+j)/2];
while(i<=j){ //i<=j都会一直循环,所以可知最后跳出循环一定是i>j
while(i<=j && nums[i]>pivot){
i++;
}
while(i<=j && nums[j]<pivot){
j--;
}
if(i<=j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
i++;
j--;
}
}
if(start+k-1<=j){ //判断出k会在左边部分,继续递归左边部分直到找到所求
return quickSelect(nums,start,j,k);
}
if(start+k-1>=i){ //判断出k会在右边部分,继续递归右边部分直到找到所求
return quickSelect(nums,i,end,k-(j-start+1));
}
return nums[j+1]; //i=j是最后一次循环,i++,j--,使得数组分为三部分
} //左边部分小于pivot,右边部分大于pivot,中间有个pivot
} //其实这时候nums[j+1]=pivot,所以返回pivot也可以
或者优先队列小顶堆方法,时间复杂度也是O(n),符合题意
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) { //方法二:小顶堆
Queue<Integer> pQueue=new PriorityQueue<>();
for(int num:nums){
pQueue.offer(num);
if(pQueue.size()>k){
pQueue.poll();
}
}
return pQueue.peek();
}
}
461. Kth Smallest Numbers in Unsorted Array:点击打开链接
class Solution {
/*
* @param k an integer
* @param nums an integer array
* @return kth smallest element
*/
public int kthSmallest(int k, int[] nums) { //方法一:quick Select
if(nums==null || nums.length==0 || k<=0){
return -1;
}
return quickSelect(nums,0,nums.length-1,k);
}
private int quickSelect(int[] nums,int start,int end,int k){
if(nums[start]==nums[end]){
return nums[start];
}
int i=start;
int j=end;
int pivot=nums[(i+j)/2];
while(i<=j){
while(i<=j && nums[i]<pivot){
i++;
}
while(i<=j && nums[j]>pivot){
j--;
}
if(i<=j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
i++;
j--;
}
}
if(start+k-1<=j){
return quickSelect(nums,start,j,k);
}
if(start+k-1>=i){
return quickSelect(nums,i,end,k-(j-start+1));
}
return pivot;
}
}
class Solution {
/*
* @param k an integer
* @param nums an integer array
* @return kth smallest element
*/
public int kthSmallest(int k, int[] nums) { //方法二:大顶堆
if(nums==null || nums.length==0 || k<=0){
return -1;
}
Queue<Integer> pQueue=new PriorityQueue<>(k,Collections.reverseOrder()); //大顶堆的写法一
for(int num:nums){
pQueue.offer(num);
if(pQueue.size()>k){
pQueue.poll();
}
}
return pQueue.peek();
}
}
class Solution {
/*
* @param k an integer
* @param nums an integer array
* @return kth smallest element
*/
public int kthSmallest(int k, int[] nums) {
if(nums==null || nums.length==0 || k<=0){
return -1;
}
Queue<Integer> pQueue=new PriorityQueue<>(k,myComparator); //大顶堆的写法二
for(int num:nums){
pQueue.offer(num);
if(pQueue.size()>k){
pQueue.poll();
}
}
return pQueue.peek();
}
private Comparator<Integer> myComparator=new Comparator<Integer>(){ //自定义比较器
public int compare(Integer a,Integer b){ //a是前一个数,b是后一个数
return b-a; //后一个数-前一个数就是从大到小
}
}; //分号不能少
}
class Solution {
/*
* @param k an integer
* @param nums an integer array
* @return kth smallest element
*/
public int kthSmallest(int k, int[] nums) { //大顶堆写法三
if(nums==null || nums.length==0 || k<=0){
return -1;
}
Queue<Integer> pQueue=new PriorityQueue<>(k,new Comparator<Integer>(){ //或者直接写自定义比较器
public int compare(Integer a, Integer b) {
return b-a;
}
});
for(int num:nums){
pQueue.offer(num);
if(pQueue.size()>k){
pQueue.poll();
}
}
return pQueue.peek();
}
}