import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

public class BinarySearch {
    public static void main(String[] args) {
        int[] a = { 11, 27, 28, 33 };
        // System.out.println(findFirstRepeat("qywyer23tdd", 11));
        // ListNode head = LinkedListReverse.initialList();
        // LinkedListReverse.printList(insertionSortList(head));[4,5,1,6,2,7,3,8],10
        GetLeastNumbers_Solution(new int[] { 4, 5, 1, 6, 2, 7, 3, 8 }, 10);
    }

    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int cnt = 0;
        if (k > input.length || k == 0) {
            return list;
        }
        while (cnt < k) {
            list.add(input[cnt]);
            cnt++;
        }
        Collections.sort(list);
        
        for (int i = k; i < input.length; i++) {
            int num = input[i];
            // 如果超出最大，则不用管，如果没有超出最大，则需要加入并踢出最大
            if (num < list.get(k - 1)) {
                list.remove(k - 1);
                list.add(num);
                Collections.sort(list);
            }
        }
        System.out.println(list);
        return null;
    }

    /**
     * 插入排序 head 1 -> 7 -> 2 -> 6 -> 9 1 -> 2 -> 6 -> 7 -> 9
     */
    public static ListNode insertionSortList(ListNode head) {
        ListNode pstart = head;
        ListNode pcurr = head.next;
        if (pstart == null) {
            return null;
        }
        // //1 7 2 6 9 3 在7后面插入888
        // do {
        // int currVal = pstart.val;
        // if (currVal == 7) {
        // ListNode newNode = new ListNode(888, null);
        // newNode.setNext(pstart.next);
        // pstart.setNext(newNode);
        // }
        // } while ((pstart = pstart.next) != null);

        // 1 7 2 6 9 3 在7前面插入888
        do {
            int currVal = pcurr.val;
            if (currVal == 7) {
                ListNode newNode = new ListNode(888, null);
                newNode.setNext(pcurr);
                pstart.setNext(newNode);
            }
        } while ((pcurr = pcurr.next) != null);
        return head;
    }

    public static char findFirstRepeat(String A, int n) {
        HashSet<Character> hs = new HashSet<Character>();
        for (char c : A.toCharArray()) {
            if (hs.contains(c)) {
                return c;
            } else {
                hs.add(c);
            }
        }
        return ‘ ‘;
    }

    public static int getPos(int[] A, int n, int val) {
        int start = 0;
        int end = n - 1;
        int mid = (end - start) / 2;
        while (start < end) {
            if (A[mid] == val) {
                return mid;
            } else if (A[mid] > val) {
                end = mid;
            } else if (A[mid] < val) {
                start = mid;
            }
            mid = start + (end - start) / 2;
        }
        return 0;
    }
}