提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

JAVA中寻找最大的K个数解法

JAVA 最大 个数 寻找 解法
2023-06-13 09:15:25 时间
这个题拿到之后首先会想到排序，排好序之后在选取选取最大的K个数。排序选择快速排序是个比较好的选择。
好了，让我们来进行第一个解法：快速排序
代码如下
复制代码代码如下:

publicstaticvoidquickSort(int[]arr,intstart,intend){
  if(start<end){
   intkey=arr[start];
   intright=start;
   intleft=end;
   while(right<left){
    while(right<left&&arr[left]>key){
     left--;
    }
    if(right<left){
     arr[right]=arr[left];
    }
    while(right<left&&arr[right]<=key){
     right++;
    }
    if(right<left){
     arr[left]=arr[right];
    }
   }
   arr[right]=key;
   quickSort(arr,start,right-1);
   quickSort(arr,left+1,end);
  }
 }
 

快速排序之后，数组会是有序的，上面的排序是从小到大的，所以我们输出应该是下面这样
复制代码代码如下:
               intk=4;
  for(inti=arr.length-1;i>=arr.length-k;i--){
   System.out.println(arr[i]+" ");
  }

。第一个解法已经好了，但是有没有更好的办法。
答案是有的！我们可以选择部分排序，接下来我们使用选择排序来做解决这个问题。
代码如下：
复制代码代码如下:publicstaticint[]selectSortK(int[]arr,intk){
  if(arr==null||arr.length==0){
   returnnull;
  }
  int[]newArr=newint[k];
  List<Integer>list=newArrayList<Integer>();//记录每次最大数的下标
  for(inti=0;i<k;i++){
   intmaxValue=Integer.MIN_VALUE;//最大值
   intmaxIndex=i;
   for(intj=0;j<arr.length;j++){
    if(arr[j]>maxValue&&!list.contains(j)){
     maxValue=arr[j];
     maxIndex=j;
    }
   }
   if(!list.contains(maxIndex)){//如果不存在，就加入
    list.add(maxIndex);
    newArr[i]=maxValue;
   }
  }
  returnnewArr;
 }

相关文章