《剑指offer》(二十九)--最小的K个数（java）

考点：时间效率、数组、高级算法

题目描述

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

代码格式

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        
    }
}

解题一-

1.思路
设置一个大小为k的容器，如果还有空余，就将数组中的数加进去，否则就比较数组中的数和容器中最大的数，选择最小的放进去。
注：ArrayList中的indexOf（int k）方法，是返回值为k的下标。
2.代码

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
   public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        int lens = input.length;
        //参数满足条件
        if(input == null || lens == 0 || k > lens || k <= 0){
            return result;
        }
        for(int i = 0; i < input.length; i++) {
            if(res.size() < k) {
                res.add(input[i]);
            }
            else {
                int max = Collections.max(res);
                if(max > input[i]) {
                    res.set(res.indexOf(max), input[i]);
                }
            }
        }
        return res;
    }
}

参考：原文链接：https://blog.csdn.net/melwx/article/details/88629440

解题二-利用快速排序的partition()方法

1.思路
（1）利用快排的partition函数,将原序列分为左右两个子序列，左边序列都小于array[index]，右边序列都大于或等于array[index]
（2）遍历数组，当array[index]为数组的第k个元素时，数组中array[index]及其之前的元素都小于右边序列，即为n个整数中最小的k个数。使用大小为k的堆，维护到目前为止最小的k个数。
2.代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        int lens = input.length;
        //参数满足条件
        if(input == null || lens == 0 || k > lens || k <= 0){
            return result;
        }
        //// 快排思想，index前面的数小于input[index]
        int index = partition(input, 0, lens-1);
        // 目标索引,此处不能以k为目标索引，因为k可能等于数组的长度，以k为索引，数组越界
        while(index != k-1){
            // 目标值在index左侧
            if(index > k-1)
                index = partition(input, 0, index-1);
            // 目标值在index右侧
            if(index < k-1)
                index = partition(input, index+1, input.length-1);
        }
        for(int i=0; i<=index; i++)
            result.add(input[i]);
        return result;
    }
    //partition()快速排序方法
    // 以array[index]为参照，比该值小的放在左侧，比该值大的放在右侧，并返回array[left]的索引
    public int partition(int[] array, int left, int right){
        int random = (int)(Math.random()*(right - left + 1)) + left;
        swap(array, random, right);
        int small = left-1;//小于区 (最开始写错了小于区的初始值!)
        int big  = right;//大于区
        while(left < big){
            if(array[left] < array[right])
                swap(array, left++, ++small);
            else if(array[left] > array[right])
                swap(array, left, --big);
            else
                left++;
        }
        swap(array, big, right);
        return big;
    }
    //swap()方法
    public void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

参考：https://blog.csdn.net/littlehaes/article/details/92805711

解题三-构建最大堆容器

1.思路
（1）使用最大堆，构建容量为K的最大堆；
（2）遍历数组，每次比较数组中的元素与堆顶元素大小，堆顶小入堆
2.代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        int lens = input.length;
        //参数满足条件
        if(input == null || lens == 0 || k > lens || k <= 0){
            return result;
        }
       
        // 构建大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2) {
                return o2.compareTo(o1);
            }
        });

        // 遍历数组，把比堆顶元素小的元素加入最大堆中
        for (int i=0; i<lens; i++) {
            int curVal = input[i];
            if (maxHeap.size() < k) {
                maxHeap.add(curVal);
            } else {
                // 堆顶元素大于当前元素，则弹出堆顶元素，加入当前元素到堆中
                if (maxHeap.peek() > curVal) {
                    maxHeap.poll();
                    maxHeap.add(curVal);
                }
            }
        }
        
        // 最大堆所有元素加入要返回的list中
        result.addAll(maxHeap);
        
        return result;
    }
    public static void main(String[] args)
    {
        int[] input = {4,5,1,6,2,7,3,8};
        System.out.println(new Solution().GetLeastNumbers_Solution(input, 4));
    }
}

参考：https://blog.csdn.net/zangdaiyang1991/article/details/90318768