1000021. Smallest K LCCI

难度: Medium

题目描述

Design an algorithm to find the smallest K numbers in an array.

Example:

Input:  arr = [1,3,5,7,2,4,6,8], k = 4
Output:  [1,2,3,4]

Note:

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

解题思路

代码实现

解决方案

java

class Solution {
    public int[] smallestK(int[] arr, int k) {
        List<Integer> res = new ArrayList<>();

        quickSort(arr, 0, arr.length - 1, k, res);
        int[] resArr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resArr[i] = res.get(i);
        }
        return resArr;
    }

    private void quickSort(int[] arr, int left, int right, int k, List<Integer> res) {
        if (right < left) {
            return;
        }
        if (res.size() == k) {
            return;
        }

        int pIdnex = partition(arr, left, right);
        if (pIdnex < k) {
            res.add(arr[pIdnex]);
        }

        quickSort(arr, left, pIdnex - 1, k, res);

        quickSort(arr, pIdnex + 1, right, k, res);

    }

    private int partition(int[] arr, int left, int right) {
        
        int povit = arr[left];
        int lo = left+1;
        int hi = right;
        while(lo<=hi){
            if(arr[lo]>povit){
               swap(arr,lo,hi--);
               continue;
            } 
            lo++;
        }
        if(lo!=left){
             swap(arr,hi,left);
            // if(arr[lo]<povit){
            //     swap(arr,lo,left);
            // }else{
            //       swap(arr,--lo,left);
            // }

        }
        return hi;
         
    }
     void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}