关于剑指 Offer 40. 最小的k个数的相关问题

波波老师，您好！

我先贴出来我的代码（基本和您的吻合）

相关代码：

/// Leetcode 剑指 Offer 40. 最小的k个数
/// https://leetcode.cn/problems/kth-largest-element-in-an-array/

import java.util.Arrays;
import java.util.Random;

class Solution {
    public int[] getLeastNumbers(int[] nums, int k) {
        Random rnd = new Random();
        selectK(nums, 0, nums.length - 1, k - 1, rnd);
        return Arrays.copyOf(nums, k);
    }

    private int selectK(int[] nums, int l, int r, int k, Random rnd) {
        int p = partition(nums, l, r, rnd);
        if (k == p) return nums[p];
        if (k < p) return selectK(nums, l, p - 1, k, rnd);
        return selectK(nums, p + 1, r, k, rnd);
    }

    private int partition(int[] nums, int l, int r, Random rnd) {
        int p = l + rnd.nextInt(r - l + 1);
        swap(nums, l, p);
        // arr[l+1...i-1] <= v; arr[j+1...r] >= v
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && nums[i] < nums[l])
                i++;
            while (j >= i && nums[j] > nums[l])
                j--;
            if (i >= j) break;
            swap(nums, i++, j--);
        }
        swap(nums, l, j);
        return j;
    }

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

测试用例是：

public class Main {
    public static void main(String[] args) {
        int[] nums = {0, 0, 0, 2, 0, 5};
        Solution solution = new Solution();
        int[] numbers = solution.getLeastNumbers(nums, 0);
        for (int i = 0; i < numbers.length; i++)
            System.out.print(numbers[i] + " ");
    }
}

报错是：

我的调试过程：

传入的数组是

{0, 0, 0, 2, 0, 5}

传入的参数是0

• selectK(nums.0,5,-1,rnd)

  • partition(nums,0,5,rnd)：p=2,返回值为j=2

  • {0, 0, , 2, 0, 5}

• k(-1)<p(j=2)，selectK(nums,0,1,-1,rnd)

  • partition(nums,0,1,rnd)：p=1,返回值为j=1

  • {0, , 0, 2, 0, 5}

• k(-1)<p(j=1)，selectK(nums,0,0,-1,rnd)

  • partition(nums,0,0,rnd)：p=0,返回值为j=0

  • {, 0, 0, 2, 0, 5}

• k(-1)<p(j=0)，selectK(nums,0,-1,-1,rnd)

  • partition(nums,0,-1,rnd)：在这里的第一行取随机数的代码就会出现索引问题

==============分界线================

波波老师，主要我觉得似乎在处理k=0的时候，无论数组是如何的，似乎都会出现这种问题。。。

下面是老师您的代码：