剑指 Offer 40. 最小的k个数

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

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

解题思路

快速排序。

public int[] getLeastNumbers(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k == 0) {
        return new int[0];
    }      
    return quickSearch(arr, 0, arr.length-1, k);
}

private int[] quickSearch(int[] arr, int lower, int upper, int k) {
    int pos = partition(arr, lower, upper);
    if (pos == k -1) {
        return Arrays.copyOf(arr, k);
    }
    return pos > k - 1 ? quickSearch(arr, lower, pos-1, k) : quickSearch(arr, pos + 1, upper, k);
}
// 这是一个直接赋值的写法
public int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    // 维持两个指针l和r, 在运动的过程中,保证l左边的元素都小于等于pivot, r右边的元素都大于pivot
    int l = left, r = right;
    while(l < r) {
        // 先把右边小于枢纽值的元素放到左边
        while(arr[r] >= pivot && l < r) r--;
        arr[l] = arr[r];
        // 再把左边大于枢纽值的元素放到右边
        while(arr[l] <= pivot && l < r) l++;
        arr[r] = arr[l];
    }
    arr[l] = pivot;
    return l;   
}

另外一种写法

public int[] getLeastNumbers(int[] arr, int k) {
    randomizedSelected(arr, 0, arr.length - 1, k);
    return Arrays.copyOf(arr, k);
}

public void randomizedSelected(int[] arr, int l, int r, int k) {
    if (l >= r) {
        return;
    }
    int pos = randomizedPartition(arr, l, r);
    int num = pos - l + 1;
    if (k == num) {
        return;
    } else if (k < num) {
        randomizedSelected(arr, l, pos - 1, k);
    } else {
        randomizedSelected(arr, pos + 1, r, k - num);
    }
}

// 基于随机的划分
public int randomizedPartition(int[] nums, int l, int r) {
    int i = new Random().nextInt(r - l + 1) + l;
    swap(nums, r, i);
    return partition(nums, l, r);
}

public int partition(int[] nums, int l, int r) {
    // 以最右边的元素做枢纽值
    int pivot = nums[r];
    int i = l - 1;
    // 从左往右扫描, 
    for (int j = l; j <= r - 1; ++j) {
        if (nums[j] <= pivot) {
            // 直到遇到一个小于枢纽值的元素, 把其交换到i的下一个位置
            i = i + 1;
            swap(nums, i, j);
        }
        // 如果遇到的值大于枢纽值, 则j指针向前走, 
        // i 指针仍然指向那个不超过枢纽值的最大元素
    }
    // 当数据遍历完成时, 所有小于枢纽值的元素全部都放到[l, i]区间了。
    // 那么只需要将枢纽值交换到 i + 1的位置, 就可以了。
    swap(nums, i + 1, r);
    return i + 1;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}