題目描述

輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,。

思路分析

兩種思路可以實(shí)現(xiàn)，第一種是利用插入排序來實(shí)現(xiàn)，首先維持一個(gè)長(zhǎng)度為K的有序序列，然后將剩下的數(shù)字插入到有序序列中去，直到最后一個(gè)元素，插入排序結(jié)束后就前面K個(gè)元素就是最小的K個(gè)數(shù)；

第二種是利用快速排序來實(shí)現(xiàn)，需要改動(dòng)一下，判斷每次返回的partition位置是否等于K，根據(jù)返回的位置下標(biāo)進(jìn)行左右遞歸分治，直到最終返回的partition位置等于K時(shí)，前面K個(gè)元素就是題目要求的最小K個(gè)數(shù)；

代碼實(shí)現(xiàn)

 import java.util.ArrayList;

public class Solution {
      /**
     * 鏈接：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion
     * 來源：牛客網(wǎng)
     * 維持一個(gè)K長(zhǎng)度的最小值集合，然后利用插入排序的思想進(jìn)行對(duì)前K個(gè)元素的不斷更新。
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {

        ArrayList<Integer> result = new ArrayList<Integer>();
        if (k <= 0 || k > input.length)
            return result;
        //初次排序，完成k個(gè)元素的排序
        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;
        }
        //遍歷后面的元素 進(jìn)行k個(gè)元素的更新和替換
        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個(gè)元素返回
        for (int i = 0; i < k; i++)
            result.add(input[i]);
        return result;
    }

    /**
     * 鏈接：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?answerType=1&f=discussion
     * 來源：?？途W(wǎng)
     * <p>
     * 快排的partition函數(shù)會(huì)將原序列分為左右兩個(gè)子序列，左邊序列都小于pivot，右邊序列都大于或等于pivot，
     * 當(dāng)pivot為數(shù)組的第k個(gè)元素時(shí)，數(shù)組中pivot及其之前的元素都小于右邊序列，即為n個(gè)整數(shù)中最小的k個(gè)數(shù)。
     */
    public ArrayList<Integer> GetLeastNumbers_SolutionV2(int[] input, int k) {
        if (input == null || input.length == 0 || input.length < k || k == 0) {
            return new ArrayList<>();
        }
        // 在數(shù)組中尋找位置為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個(gè)數(shù)
        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));
    }
}

歡迎關(guān)注南閣公眾號(hào)

南閣子也