剑指offer-面试题40：最小的K个数

题目描述

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

思路分析

两种思路可以实现，第一种是利用插入排序来实现，首先维持一个长度为K的有序序列，然后将剩下的数字插入到有序序列中去，直到最后一个元素，插入排序结束后就前面K个元素就是最小的K个数；

第二种是利用快速排序来实现，需要改动一下，判断每次返回的partition位置是否等于K，根据返回的位置下标进行左右递归分治，直到最终返回的partition位置等于K时，前面K个元素就是题目要求的最小K个数；

代码实现

 import java.util.ArrayList;

public class Solution {
      /**
     * 链接：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion
     * 来源：牛客网
     * 维持一个K长度的最小值集合，然后利用插入排序的思想进行对前K个元素的不断更新。
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {

        ArrayList<Integer> result = new ArrayList<Integer>();
        if (k <= 0 || k > input.length)
            return result;
        //初次排序，完成k个元素的排序
        for (int i = 1; i < k; i++) {
            int j = i - 1;
            int unFindElement = input[i];
            while (j >= 0 && input[j] > unFindElement) {
                input[j + 1] = input[j];
                j--;
            }

            input[j + 1] = unFindElement;
        }
        //遍历后面的元素 进行k个元素的更新和替换
        for (int i = k; i < input.length; i++) {
            if (input[i] < input[k - 1]) {
                int newK = input[i];
                int j = k - 1;
                while (j >= 0 && input[j] > newK) {
                    input[j + 1] = input[j];
                    j--;
                }
                input[j + 1] = newK;
            }
        }
        //把前k个元素返回
        for (int i = 0; i < k; i++)
            result.add(input[i]);
        return result;
    }

    /**
     * 链接：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion
     * 来源：牛客网
     * <p>
     * 快排的partition函数会将原序列分为左右两个子序列，左边序列都小于pivot，右边序列都大于或等于pivot，
     * 当pivot为数组的第k个元素时，数组中pivot及其之前的元素都小于右边序列，即为n个整数中最小的k个数。
     */
    public ArrayList<Integer> GetLeastNumbers_SolutionV2(int[] input, int k) {
        if (input == null || input.length == 0 || input.length < k || k == 0) {
            return new ArrayList<>();
        }
        // 在数组中寻找位置为k - 1的pivot
        int start = 0, end = input.length - 1;
        int index = partition(input, start, end);
        while (index != k - 1) {
            if (index < k - 1) {
                start = index + 1;
            } else {
                end = index - 1;
            }
            index = partition(input, start, end);
        }

        // 收集这k个数
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i <= index; i++) {
            res.add(input[i]);
        }
        return res;
    }

    // divide target range array to smaller hi value part and other part.
    private int partition(int[] arr, int start, int end) {
        int pivot = arr[end];
        int prePtr = start - 1;
        while (start < end) {
            if (arr[start] < pivot) {
                swap(arr, start++, ++prePtr);
            } else {
                start++;
            }
        }
        swap(arr, end, ++prePtr);
        return prePtr;
    }


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

    public static void main(String[] args) {
        int[] array = {4, 5, 1, 6, 2, 7, 3, 8};
        Q40_MinimumNumberOfK q40MinimumNumberOfK = new Q40_MinimumNumberOfK();
        //        ArrayList<Integer> arrayList = solution23.GetLeastNumbers_Solution(array, 4);
        ArrayList<Integer> arrayList = q40MinimumNumberOfK.GetLeastNumbers_SolutionV2(array, 4);
        System.out.println(arrayList);
        System.out.println(Arrays.toString(array));
    }
}

欢迎关注南阁公众号

南阁子也