思路:
题目说不是第k个不同的元素,即重复的元素算多个,类似rank() 或者 Row_number(),而不是Dense_number()
使用最大优先队列(堆),poll() 第k次返回的即为第k大的数;
或者最小优先队列,poll()第n-k+1次即为第k大的数;
而使用数组,第k大的数,即nums数组中n-k索引的元素;
注意:Queue的方法,poll()会删除元素,peek()不会删除元素;
方法一:最大、最小优先队列
最大优先队列:
需要传入Comparator匿名内部类,重写compare方法;
class Solution {
public int findKthLargest(int[] nums, int k) {
int n=nums.length;
PriorityQueue<Integer> p=new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer o1,Integer o2){
return o2-o1; // 若o1 o2反过来则是从大到小排列
}
});
for(int i=0;i<n;i++){
p.add(nums[i]);
}
int r=0;
for(int j=0;j<k;j++ ){
r=p.poll();
}
return r;
}
}
最小优先队列:
class Solution {
public int findKthLargest(int[] nums, int k) {
int n=nums.length;
PriorityQueue<Integer> p=new PriorityQueue<>();
for(int i=0;i<n;i++){
p.add(nums[i]);
}
int r=0;
for(int j=0;j<n-k+1;j++ ){
r=p.poll();
}
return r;
}
}
方法二:排序
冒泡:(超时)
class Solution {
public int findKthLargest(int[] nums, int k) {
// 冒泡
for(int i=nums.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(nums[j]>nums[j+1]){
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
int n=nums.length;
return nums[n-k];
}
}
快排:
class Solution {
public int findKthLargest(int[] nums, int k) {
// 快排
sort(nums);
int n=nums.length;
return nums[n-k];
}
void sort(int[] nums ){
int lo=0;
int hi=nums.length-1;
sort(nums,lo,hi);
}
void sort(int[] nums,int lo,int hi){
if(lo>=hi){
return;
}
// 前序
int partition=partition(nums,lo,hi);
sort(nums,lo,partition-1);
sort(nums,partition+1,hi);
}
int partition(int[] nums,int lo,int hi){
int key=nums[lo];
int left=lo;
int right=hi+1;
while(true){
while(nums[--right]>key){
if(right<=lo){
break;
}
}
while(nums[++left]<key){
if(left>=hi){
break;
}
}
if(left>=right){
break;
}else{
swap(nums,left,right);
}
}
swap(nums,lo,right);
return right;
}
void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/89233.html