最小的K个数

二刷
大根堆

import java.util.ArrayList;

public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (input == null || input.length == 0 || k > input.length || k == 0)
            return list;
        int[] heap =new int[k];
        for(int i=0;i<k;i++)
            heap[i] = input[i];

        buildMaxHeap(heap,k);
        for(int i=k;i<input.length;i++){
            if(input[i] < heap[0]){
                heap[0] = input[i];
                heapify(heap,k,0);
            }
        }

        for (int i = 0; i < heap.length; i++) {
            list.add(heap[i]);
        }
        return list;
    }

    public void buildMaxHeap(int[] heap, int len){
        for(int i = len/2-1;i>=0;i--){
            heapify(heap,len,i);
        }
    }

    public void heapify(int[] heap, int len, int k){
        int leftc = 2*k+1;
        int rightc = 2*k+2;
        int largest = k;
        // 这块别乱
        if(leftc<len && heap[leftc] > heap[largest]) largest = leftc;
        if(rightc<len && heap[rightc] > heap[largest]) largest = rightc;
        if(largest !=k) {
            swap(heap,k,largest);
            heapify(heap,len,largest);
        }
    }

    public void swap(int[] nums, int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

一定先是j-- 后是i++；
否则 这行
while(i<j && nums[i] < nums[l] ) i++;
把等号去掉 不用在意顺序

import java.util.ArrayList;

public class Solution {
    int[] nums;
    int target = -1;
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        this.nums = input;
        partition(0,input.length-1,k-1);
        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i=0;i<input.length;i++){
            if(nums[i]<target) list.add(nums[i]);
        }
        for(int count = list.size();count<k;count++){
            list.add(target);
        }
        return list;

    }
    public void partition(int l, int r, int k){
        if(l>r) return ;
        int i=l;
        int j=r;
        while(i<j){
            while(i<j && nums[j] >= nums[l])  j--;
            while(i<j && nums[i] <= nums[l] ) i++;
            swap(i,j);
        }
        swap(i,l);
        if(i==k) target=nums[i];
        else if(i>k)  partition(l,i-1,k);
        else  partition(i+1,r,k);

    }
    public void swap(int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

NC88 最大k个 同理

1.快排做法
partition 每次确定一个数的位置

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(k==0){return list;}
        int min_num = minK(input,0,input.length-1,k-1);
        int count = 0;
        for(int i = 0; i < input.length ;i++){
            if(input[i]<min_num){
                list.add(input[i]);
                count++;
            }
        }
        while(count<k){
            list.add(min_num);
            count++;
        }
        return list;
    }

    public int minK(int[] nums, int l, int r, int k){
        int random = l + (int) (Math.random() * ( r-l+1));
        int[] range = partition(nums, l, r, nums[random]);
        if(k<=range[1] && k>=range[0]){
            return nums[k];
        }
        else if(k<range[0]){
            return minK(nums,l,range[0]-1,k);
        }
        else{
            return minK(nums,range[1]+1,r,k);
        }
    }

    public int[] partition(int[] nums, int l, int r, int pivot){
        if(l==r){
            int[] range = {l, r};
            return range;
        }
        int less = l;
        int more = r;
        int cur = l;
        while(cur<= more){
            if(nums[cur]>pivot){
                swap(nums,cur,more);
                more--;
            }
            else if(nums[cur]<pivot){
                swap(nums,cur,less);
                less++;cur++;
            }
            else{
                cur++;
            }
        }
        int[] range = {less, more};
        return range;
    }
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

2. 大根堆

完全二叉树 性质
heapify 调整堆化
buildMaxHeap 从最后一个节点的父节点开始调整

import java.util.ArrayList;
import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || input.length == 0 || k > input.length || k == 0)
            return list;
        int[] arr = new int[k];
        //初始化数组
        for (int i = 0; i < k; i++)
            arr[i] = input[i];
        buildMaxHeap(arr, k);//构造大根堆
        for (int i = k; i < input.length; i++) {
            if (input[i] < arr[0]) {
                arr[0] = input[i];
                heapify(arr, k, 0);//将改变了根节点的二叉树继续调整为大根堆
            }
        }
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
        return list;
    }

    public void buildMaxHeap(int[] arr, int k){
        for(int i=k/2-1; i>=0; i--){
            heapify(arr,k,i);
        }
    }

    public void heapify(int[] arr, int length, int k ){
        int leftchild = 2*k + 1;
        int rightchild = 2*k + 2;
        int larget = k;
        if(leftchild<length && arr[larget]<arr[leftchild]){
            larget = leftchild;
        }
        if(rightchild<length && arr[larget]<arr[rightchild]){
            larget = rightchild;
        }
        if(larget != k){
            swap(arr,larget,k); // 需要调整被交换的节点
            heapify(arr, length, larget);
        }
    }

    public void swap(int[] arr, int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}