• 最小的K个数
    • 题目
    • 解题思路
      • Partition
      • 小根堆算法

    最小的K个数

    题目

    牛客网

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

    解题思路

    Partition

    该算法基于 Partition

    1. public ArrayList<Integer> GetLeastNumbers_Solution_Partition(int[] input, int k) {
    2.     ArrayList<Integer> res = new ArrayList<>();
    4.     if (k > input.length || k < 1) {
    5.         return res;
    6.     }
    8.     int start = 0, end = input.length - 1;
    9.     int index = partition(input, start, end);
    10.     while (index != k - 1) {
    11.         if (index > k - 1) {
    12.             end = index - 1;
    13.             index = partition(input, start, end);
    14.         } else {
    15.             start = index + 1;
    16.             index = partition(input, start, end);
    17.         }
    18.     }
    20.     for (int i = 0; i < input.length && i < k; i++) {
    21.         res.add(input[i]);
    22.     }
    23.     return res;
    24. }
    26. private int partition(int[] nums, int start, int end) {
    27.     int left = start, right = end;
    28.     int key = nums[left];
    30.     while (left < right) {
    31.         while (left < right && nums[right] > key) {
    32.             right--;
    33.         }
    34.         if (left < right) {
    35.             nums[left] = nums[right];
    36.             left++;
    37.         }
    39.         while (left < right && nums[left] <= key) {
    40.             left++;
    41.         }
    42.         if (left < right) {
    43.             nums[right] = nums[left];
    44.             right++;
    45.         }
    46.     }
    48.     nums[left] = key;
    50.     return left;
    51. }

    小根堆算法

    该算法基于小根堆，适合海量数据，时间复杂度为：n*logk

    1. public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    2.     ArrayList<Integer> res = new ArrayList<>();
    3.     if (k > input.length||k==0) {
    4.         return res;
    5.     }
    7.     for (int i = input.length - 1; i >= 0; i--) {
    8.         minHeap(input, 0, i);
    10.         swap(input, 0, i);
    12.         res.add(input[i]);
    13.         if (res.size() == k) break;
    14.     }
    15.     return res;
    16. }
    18. private void minHeap(int[] heap, int start, int end) {
    19.     if (start == end) {
    20.         return;
    21.     }
    23.     int childLeft = start * 2 + 1;
    24.     int childRight = childLeft + 1;
    26.     if (childLeft <= end) {
    27.         minHeap(heap, childLeft, end);
    29.         if (heap[childLeft] < heap[start]) {
    30.             swap(heap, start, childLeft);
    31.         }
    32.     }
    34.     if (childRight <= end) {
    35.         minHeap(heap, childRight, end);
    37.         if (heap[childRight] < heap[start]) {
    38.             swap(heap, start, childRight);
    39.         }
    40.     }
    41. }
    43. private void swap(int[] nums, int a, int b) {
    44.     int t = nums[a];
    45.     nums[a] = nums[b];
    46.     nums[b] = t;
    47. }