牛客网--最小的k个数（堆排序）

爱被打了一巴掌 2022-05-08 15:03 189阅读 0赞

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字
    是1,2,3,4,。

这个一时没找到好的解决方法，只能用排序。  
但其实这道题可以用快速排序做，但快速排序的index到k-1位置时，左边数组即为所求  
真的是没掌握好排序，所以没联系到快排。  
代码如下：

package 剑指offer;
    
    import org.junit.Test;
    
    import java.lang.reflect.Array;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.TreeSet;
    
    /**
     * Created by Administrator on 2018/10/14.
     */
    public class 最小的K个数 {
        public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
           /*我的解决
           ArrayList<Integer> res=new ArrayList<>();
            if(k<=0||k>input.length)
                return res;
            Arrays.sort(input);
            for(int i=0;i<k;i++){
                res.add(input[i]);
            }
            return res;*/
            
            if(k<=0||input==null||k>input.length)
                return new ArrayList<>();
            return quickSort(input,k);
        }
    
        public static ArrayList<Integer> quickSort(int[] input,int k){
            /*
            利用快速排序找出k个最小的数组，
            在k-1位置时，左边数组即为所求
            <k-1时，low指针向右移动
            >k-1时，high指针向左移动
             */
            ArrayList<Integer> res=new ArrayList<>();
            int low=0,high=input.length-1;
            int index=paration(input,low,high);
            while(index!=k-1){
                if(index<k-1){
                    low=index+1;
                }else{
                    high=index-1;
                }
                index=paration(input,low,high);
            }
            for(int i=0;i<k;i++)
                res.add(input[i]);
            return res;
        }
    
        private static int paration(int[] input, int low, int high) {
            int tmp=input[low];
            while (low<high){
                while (high>low&&input[high]>tmp)
                    high--;
                input[low]=input[high];
                while (low<high&&input[low]<tmp)
                    low++;
                input[high]=input[low];
            }
            input[low]=tmp;
            return low;
        }
    
        @Test
        public void test(){
            int[] inputs={4,5,1,6,2,7,3,8};
            ArrayList<Integer> res=GetLeastNumbers_Solution(inputs,4);
            for (int i=0;i<4;i++){
                System.out.println(res.get(i));
            }
        }
    }

**这种方法会改变原数组中数据之间的相对位置，所以输出结果不是排好序的，但复杂度能达到O(n)，非常快**

反观我的算法，会改变原数组，这是不太好的，一般不要改变输入的数组，写的时候也没注意到这点。  
可以用TreeSet,底层是红黑树，按排列顺序输出，复杂度O(nlogn),和一般排序算法差不多。

private static ArrayList<Integer> treeSet(int[] input,int k){
            if(input == null)
                return null;
            ArrayList<Integer> list = new ArrayList<Integer>(k);
            if(k > input.length) return list;
            TreeSet<Integer> tree = new TreeSet<Integer>();
            for(int i = 0; i < input.length; i++){
                tree.add(input[i]);
            }
            int i = 0;
            for(Integer elem : tree){
                if(i >= k)
                    break;
                list.add(elem);
                i++;
            }
            return list;
    
        }

可以自己实现最大堆找出最小的k个数  
[参考博客][Link 1]  
堆排序学的不是太好，有必要自己实现一下  
[堆排序][Link 2]

**堆排序**  
用数组实现效率比较高  
说下基本要注意的  
用数组x实现

*  root=1 下标1开始，作为根
 *  value(i)=x\[i\]
 *  leftChild(i)=2\*i
 *  rightCild(i)=2\*i+1
 *  parent(i)=i/2
 *  null(i)=(i<1) or (i>n)
 *  topN问题采用容量为n的最小堆，minN相反

## 实现 ##

public class heapSort {
    
        public heapSort(){
    
        }
    
        public heapSort(int[] arr){
            /*
            * 构建最大堆
            * */
            for(int i=1;i<arr.length;i++)
                shitUp(arr,i);
        }
    
        public int[] minK(int[] arr,int k){
            /*
            构建容量为k的最大堆
            * 实现时忘记了topK是要用最小堆的，
            * 所以将就minK
            * */
            int[] res=new int[k+1];
            for(int i=1;i<=k;i++){
                res[i]=arr[i];
            }
            BuildMaxHeap(res,k);
            for(int i=k;i<arr.length;i++){
                if(arr[i]>res[1])
                    continue;
                else{
                    res[1]=arr[i];
                    shitDown2(res,1,k);
                }
            }
            return res;
        }
    
        private void shitUp(int[] arr,int n){
            /*
            * 这种适合构建堆
            * 假设有一个最大堆，从堆得最后面即
            * 数组末尾开始向上寻找合适位置
            * */
            while(true){
                if(n==1)
                    break;
                int i=n/2;  //父节点
                if(arr[i]<=arr[n])
                    break;
                    //交换父子节点
                int tmp=arr[i];
                arr[i]=arr[n];
                arr[n]=tmp;
                n=i;
            }
        }
    
        private void shitDown1(int[] arr,int n){
            /*
            * 这种方法适合构造包含一定数量的堆
            * 需要传入参数k
            * 用以解决min(n)问题
            * 这是经典写法
            * 对于已经是n容量的堆才适合
            * 这里太麻烦，所以没打算实现
            * */
            int i=1;
            while(true){
                int c=i>>2;
                if(c>n)
                    break;
                //c是左节点
                if(c+1<n&&arr[c+1]<arr[c])
                    c++;
                if(arr[i]<=arr[c])
                    break;
                int tmp=arr[i];
                arr[i]=arr[c];
                arr[c]=tmp;
                i=c;
            }
        }
    
        private void shitDown2(int[] arr,int s,int n){
            /*
            * 看到的一种很好的解决minN问题
            * */
            arr[0]=arr[s];
            for(int i=s*2;i<=n;i*=2){
                if(i<n&&arr[i]<arr[i+1])
                    i++;
                if(arr[0]>=arr[i])
                    break;
                else{
                    arr[s]=arr[i];
                    s=i;
                }
            }
            arr[s]=arr[0];
        }
    
        void BuildMaxHeap(int[] arr,int n)
        {
            for(int i=n/2;i>0;i--)
                shitDown2(arr,i,n);//向下调整
        }
    
        public static void main(String[] args){
            int[] arr={0,35,40,26,51,19,23,29,17,22,18,15,20};
            heapSort sort=new heapSort(arr);
            /*for(int i=1;i<arr.length;i++)
                System.out.println(arr[i]);*/
            int k=3;
            int[] b=sort.minK(arr,k);
            for(int i=1;i<=k;i++){
                System.out.println(b[i]);
            }
        }
    
    }

最大堆和最小堆可以用PriorityQueue实现

private PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>(new Comparator<Integer>() {
           @Override
           public int compare(Integer o1, Integer o2) {
               return o1-o2;
           }
       }),
        maxHeap=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return 02-o1;
            }
        });

[Link 1]: https://blog.csdn.net/shakespeare001/article/details/51280814
[Link 2]: https://www.cnblogs.com/chengxiao/p/6129630.html