美团算法合集

class Solution {
    int k;
    Random r=new Random();
    public int[] smallestK(int[] arr, int _k) {
        k = _k;
        int n = arr.length;
        int[] ans = new int[k];
        if (k == 0) return ans;
        partition(arr, 0, n - 1);
        for (int i = 0; i < k; i++) ans[i] = arr[i];
        return ans;

    }
    void swap(int[]nums,int left,int right)
    {
        int temp=nums[left];
        nums[left]=nums[right];
        nums[right]=temp;
    }

    void partition(int[]nums,int left,int right)
    {
        if(left>=right)return;
        int pivotIndex=left+r.nextInt(right-left+1);
        swap(nums, left, pivotIndex);
        int i=left+1;
        int j=right;
        while(i<=j)
        {
            while(i<=j&&nums[i]<nums[left])
            {
                i++;
            }
            while(i<=j&&nums[j]>nums[left])
            {
                j--;
            }
            if(i>j)
            {
                break;
            }
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, left, j);
        if(j>k)partition(nums, left, j-1);
        if(j<k)partition(nums, j+1, right);
    }
}