剑指Offer-最小的K个数

Dear 丶 2022-02-21 16:54 236阅读 0赞

## 题目描述 ##

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

解题思路—**快排**：**时间复杂度O(*nlogn*)**，先将数组进行快速排序，然后取前k个数。  
解题思路—**冒泡排序**：**时间复杂度O(*n×k*)**，因为只取前k个数，所以冒泡排序的外部循环只要k次即可。  
解题思路—**堆排序**：**时间复杂度O(nlogk)**，Java中PriorityQueue的逻辑结构是一棵完全二叉树，存储结构其实是一个数组。**PriorityQueue默认是一个小顶堆**，但是可以**重写Comparator接口的compare方法**来实现大顶堆。

> 注：compare返回的int值有三种类型，compare(对象1, 对象2)  
> 负整数：对象1排在前  
> 0：位置不变  
> 正整数：对象1排在后

解题思路—**Partition思想**：**时间复杂度O(*n*)**，这是基于快速排序的改进版，只需要找到数组中排序第k的值，最后遍历数组，输出小于等于k的值即可。

## Java解题—快排 ##

import java.util.ArrayList;
    import java.util.Arrays;
    public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list = new ArrayList<>();
            if(input.length<k || k==0 || input.length==0)
                return list;
            if(input.length==k){
                for(int i:input)
                    list.add(i);
                return list;
            }
            Arrays.sort(input);
            for(int i=0;i<k;i++)
                list.add(input[i]);
            return list;
        }
    }

## Java解题—堆排序 ##

import java.util.ArrayList;
    import java.util.PriorityQueue;
    import java.util.Comparator;
    public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list = new ArrayList<>();
            if(input.length<k || k==0 || input.length==0)
                return list;
            if(input.length==k){
                for(int i:input)
                    list.add(i);
                return list;
            }
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
                @Override // 实现大顶堆
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
    
            for(int i:input){
                if(maxHeap.size()<k)
                    maxHeap.add(i);
                else if(maxHeap.peek()>i){
                    maxHeap.poll();
                    maxHeap.add(i);
                }
            }
            for(int i:maxHeap)
                list.add(i);
            return list;
        }
    }

## Java解题—冒泡排序 ##

## Java解题—Partition思想 ##

import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list = new ArrayList<>();
            if(input.length<k || k==0 || input.length==0)
                return list;
            if(input.length==k){
                for(int i:input)
                    list.add(i);
                return list;
            }
            int mid = k-1;
            int start = 0;
            int end = input.length - 1;
    
            int index = Partition(input, start, end);
    
            while(index!=mid){
                if(index<mid){
                    start = index + 1;
                    index = Partition(input, start, end);
                }else{
                    end = index - 1;
                    index = Partition(input, start, end);
                }
            }
    
            for(int i:input)
                if(i<input[k-1])
                    list.add(i);
            list.add(input[k-1]);
            return list;
        }
    
        public int Partition(int[] input, int start, int end){
            int mid = input[start];
            while(start<end){
                while(start<end && input[end]>=mid)
                    end--;
                input[start] = input[end];
                while(start<end && input[start]<=mid)
                    start++;
                input[end] = input[start];
            }
            input[start] = mid;
            return start;
        }
    }