最小的K个数

手写了一个双向链表来维护顺序。其实挺简单，但是过程也暴露了很多问题，基础不牢。。

java

import java.util.*;


public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        int n = input.length;
        if (n == 0 || k > n || k == 0) return new ArrayList<>();
        ListNode.init(k);
        for (int i = 0; i < n; i++) {
            ListNode.add(new ListNode(input[i]));
        }
        return ListNode.toList();
    }

}

class ListNode {
    private int val;
    private static int size;
    private static int maxSize;
    private ListNode next;
    private ListNode pre;

    public static ListNode head;
    public static ListNode tail;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
        this.pre = null;
    }

    //为static变量初始化
    static {
        size = 0;
        head = new ListNode(-1);
        tail = new ListNode(-2);
        head.next = tail;
        tail.pre = head;
    }
    public static void init(int maxS){
        maxSize = maxS;
    }

    public static void addLast(ListNode node) {
        node.pre = tail.pre;
        node.pre.next = node;
        node.next = tail;
        tail.pre =  node;
        size++;
    }

    public static int peek() {
        if (size!=0) {
            return tail.pre.val;
        } else return -1;
    }

    public static void removeLast() {
        if (size == 0) return;
        ListNode node = tail.pre;
        tail.pre = node.pre;
        node.pre.next = tail;
        size--;
    }

    public static void insert(ListNode node) {
        ListNode cur = head.next;
        while (cur != tail) {
            if (node.val <= cur.val) {
                node.pre = cur.pre;
                node.pre.next = node;
                node.next = cur;
                cur.pre = node;
                size++;
                return;
            }
            cur = cur.next;
        }
    }

    public static void add(ListNode node){
        // 当新增节点值大于当前列表最大值，且列表未满时，直接添加到末尾
        if(node.val>=peek()&&size<maxSize){
            addLast(node);
        }else if(node.val<peek()){      //若新增节点值小于当前列表最大值，插入到合适位置，若当前列表已满，删除末尾节点

            insert(node);
            if(size>maxSize){
                removeLast();
            }
        }
    }

    public static ArrayList<Integer> toList(){
        ArrayList<Integer> res = new ArrayList<>();
        ListNode cur = head.next;
        while(cur!=tail){
            res.add(cur.val);
            cur = cur.next;
        }
        return res;
    }
}

public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        // https://www.cainiaojc.com/java/java-priorityqueue.html
        //默认小根堆
        // 自定义 大根堆 (a, b) -> Integer.compare(b, a)
        PriorityQueue<Integer> numbers = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        if(k==0) return new ArrayList<Integer>();
        for(int i=0;i<input.length; i++){
            if(numbers.size()<k){
                numbers.add(input[i]);
            } else if(input[i] < numbers.peek()) {
                numbers.poll();
                numbers.add(input[i]);
            }
        }
        return new ArrayList<>(numbers);
    }

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

    public void push(ArrayList<Integer> list,int p,int k){
        if(list.size() >= k){
            if(p >= list.get(list.size()-1)){
                return;
            }
            list.remove(k-1);
        }
        int i =0,j=list.size()-1;
        while(i<=j){
            int m = (i+j)/2;
            if(list.get(m) > p){
                j = m-1;
            }else if(list.get(m) < p){
                i = m+1;
            }else{
                i=m;
                break;
            }
        }
        list.add(i,p);
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型一维数组 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        // 核心思想：采用传统堆，至少能够达到O(NlogN)的时间复杂度
        // 至于如何达到O(NlogK)，应当是改进堆，使之仅仅只有K个元素

        // 题解中的方法：先把前K个元素建大根堆，然后往后遍历，若小于堆顶元素，则堆顶出堆，新元素入堆
        // 遍历结束后，这K个元素就是最小的K个元素

        // 0.处理特殊情况
        ArrayList<Integer> result = new ArrayList<>();
        if (k == 0) {
            return result;
        }

        // 1.创建并初始化大根堆，前K个元素入堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < k; i++) {
            pq.add(input[i]);
        }

        // 2.往后遍历数组，尝试用更小的元素替换掉堆中的最大元素
        for (int i = k; i < input.length; i++) {
            if (input[i] < pq.peek()) {
                // 若当前元素小于堆中最大元素，则弹出最大元素，让当前元素入堆顶替
                pq.poll();
                pq.add(input[i]);
            }
        }

        // 3.此时堆中的k个元素就是所求的k个最小值
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        
        return result;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->{
           return b - a;
        });
        for (int num : input) {
            q.offer(num);
            while (q.size() > k) {
                q.poll();
            }
        }

        ArrayList<Integer> res = new ArrayList<>();
        while (!q.isEmpty()) {
            res.add(q.poll());
        }
        return res;
    }
}

// 使用java大根堆
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型一维数组 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        if (input == null || input.length == 0 || k <= 0 || k > input.length) {
            return new ArrayList<>();
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2)-> o2-o1);
        int index = 0;
        for (; index < k; index++) {
            maxHeap.add(input[index]);
        }
        while(index < input.length) {
            if (input[index] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.add(input[index]);
            }
            index++;
        }
        return new ArrayList<Integer>(maxHeap);
    }
}

public class Solution {
    /**
     * 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数

     * 使用优先队列PriorityQueue
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        if (input.length < k || k == 0) {
            return result;
        }
        PriorityQueue<Integer> que = new PriorityQueue<>(new MyComparator());
        for (int i = 0; i < input.length; i++) {
            if (que.size() < k) {
                que.offer(input[i]);
                continue;
            }
            if (input[i] < que.peek()) {
                que.poll();
                que.offer(input[i]);
            }
        }
        while (!que.isEmpty()) {
            result.add(que.poll());
        }
        return result;
    }

    //PriorityQueue默认从小到大输出，这里自定义比较器让其从大到小输出
    class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer i1, Integer i2) {
            return i2 - i1;
        }

    }

}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (k == 0 || input == null || input.length == 0) {
            return arrayList;
        }
        ArrayList<Integer> copy = new ArrayList<>();
        for (int i = 0; i < input.length; i++) {
            copy.add(input[i]);
        }
        for (int times = 0; times < k; times++) {
            Integer min = copy.get(0);
            for (int i = 1; i < copy.size(); i++) {
                if (copy.get(i) < min) {
                    min = copy.get(i);
                }
            }
            copy.remove(min);
            arrayList.add(min);
        }
        return arrayList;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        BuildHeap(input);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }
    public void adjustHeap(int[] input, int index, int length) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int minmum = index;
        if (left < length && input[left] > input[minmum]) {
            minmum = left;
        }
        if (right < length && input[right] > input[minmum]) {
            minmum = right;
        }
        if (minmum != index) {
            int temp = input[index];
            input[index] = input[minmum];
            input[minmum] = temp;
            adjustHeap(input, minmum, length);
        }
    }
    public void BuildHeap(int[] input) {
        int length = input.length;
        int index = length / 2 - 1;
        while (index >= 0) {
            adjustHeap(input, index, length);
            index--;
        }
        for (int i = length - 1; i > 0; i--) {
            int temp = input[0];
            input[0] = input[i];
            input[i] = temp;
            adjustHeap(input, 0, i);
        }
    }
}

public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // 堆排序，大根堆（堆顶元素为最大值），堆长度为K
        //堆顶就是K个数字中的最大值，如果即将进入的元素小于堆顶元素，那就直接替换堆顶元素
        //复杂度为log(n)
        //将input的前k个元素加入大根堆，然后比较后面的元素和堆顶元素大小，更新堆顶元素
        //最后，大顶堆的k个元素就是前k小个元素
        ArrayList<Integer> ans=new ArrayList<>();
        if(k==0||input.length<=0){
            return ans;
        }
        PriorityQueue<Integer> q=new PriorityQueue<>((o1,o2)->o2.compareTo(o1));//大根堆
        for(int i=0;i<k;i++){
            q.offer(input[i]);
        }
        //比较后续元素
        for(int i=k;i<input.length;i++){
            if(input[i]<q.peek()){
                q.poll();
                q.offer(input[i]);
            }
        }
        //从堆中取出元素，返回答案
        for(int i=0;i<k;i++){
            ans.add(q.poll());
        }
        return ans;
    }

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        Arrays.sort(input);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++)
            res.add(input[i]);
        return res;
    }
}

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(k==0) return list;
                //双栈一遍过
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        stack1.add(input[0]);
        for(int i=1;i<input.length;i++){
            while(!stack1.isEmpty() && input[i]<stack1.peek()){
                stack2.add(stack1.pop());
            }
            if(stack1.isEmpty() || (stack1.peek()<=input[i] && stack1.size()<k))
            {
                stack1.add(input[i]);
            }
            while(!stack2.isEmpty() && stack1.size()<k){
                stack1.add(stack2.pop());
            }
            while(!stack2.isEmpty()) stack2.pop();
        }

        while(!stack1.isEmpty()){
            stack2.add(stack1.pop());
        }
        while(!stack2.isEmpty()){
            list.add(stack2.pop());
        }
        return list;

    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;```
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList res = new ArrayList();
for (int i = 0; i < input.length; i++) {
res.add(input[i]);
}
Collections.sort(res);
System.out.println(res);
List integers = res.subList(0, k);
return new ArrayList(integers);
}
}

```

public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList res = new ArrayList();
for (int i = 0; i < input.length; i++) {
res.add(input[i]);
}
Collections.sort(res);
System.out.println(res);
List integers = res.subList(0, k);
return new ArrayList(integers);
}
}

import java.util.*;
import java.util.stream.Collectors;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        return (ArrayList<Integer>) Arrays.stream(input).sorted().limit(k).boxed().collect(Collectors.toList());
    }
}