力扣经典笔试题 最小K个数 小根堆 大根堆 快速排序 一题多解

Problem: 面试题 17.14. 最小K个数

👩‍🏫 三叶题解

🍻 大根堆版

class Solution {
	public int[] smallestK(int[] arr, int k)
	{
		PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);// 大根堆
		int[] ans = new int[k];
		if (k == 0)
			return ans;
		for (int x : arr)
		{
			if (heap.size() >= k && x >= heap.peek())// 当前元素值大于堆顶元素值
				continue;
			if (heap.size() >= k)
				heap.poll();
			heap.add(x);
		}
		for (int i = k - 1; i >= 0; i--)
		{
			ans[i] = heap.poll();
		}
		return ans;
	}
}

🍻 快速排序

class Solution {
//	快速选择
	int k;

	public int[] smallestK(int[] arr, int _k)
	{
		k = _k;
		int n = arr.length;
		int[] ans = new int[k];
		qsort(arr, 0, n - 1);
        for(int i = 0; i < k; i++)
            ans[i] = arr[i];
		return ans;
	}

	private void qsort(int[] arr, int left, int right)
	{
		if (left >= right)
			return;
		int l = left, r = right;
		int m = new Random().nextInt(right - left + 1) + left;// 随机选取标准值（划分点）下标
		swap(arr, m, left);// 把划分点放在当前区间的第一个位置
//		快速排序（划分区间）
		int x = arr[left];
		while (l < r)
		{
			while (l < r && arr[r] >= x)// 找出右区间小于划分点的元素
				r--;
			while (l < r && arr[l] <= x)// 找出左区间大于划分点的元素
				l++;
			swap(arr, l, r);
		}
		swap(arr, l, left);// 把之前放在第一个位置的划分点放在中点上
		if (l > k)// 左区间超过 k 个元素，说明前 k 小肯定在左区间
			qsort(arr, left, l - 1);
		if (l < k)
			qsort(arr, l + 1, right);
	}

	/**
	 * 交换数组左右下标的值
	 * 
	 * @param arr 数组
	 * @param l   左下标
	 * @param r   右下标
	 */
	private void swap(int[] arr, int l, int r)
	{
		int t = arr[l];
		arr[l] = arr[r];
		arr[r] = t;
	}

}

🍻 快排免swap版

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if(k == 0) return new int[]{};
        qselect(arr, 0, arr.length - 1, k - 1);
        return Arrays.copyOfRange(arr, 0, k);
    }
    public void qselect(int[] arr, int left, int right, int k) {
        if(left >= right) return;

        int pivot = pratition(arr, left, right);
        if(pivot == k){
            return;
        }else if (pivot < k){
            qselect(arr, pivot + 1, right, k);
        }else{
            qselect(arr, left, pivot - 1, k);
        }
    }
   // THU DSA 的快排模板，无需swap
    public int pratition(int[] arr, int left, int right) {
        //首先备份我们的pivot，这里简单的选择第一个，如果需要避免最坏情况，前面可以shuffle一下
        int pivot = arr[left];
       //双指针左右靠拢
        while(left < right) {
           //先做右手边！因为我们备份了左指针当前的元素为pivot的，所以先搜索右边
          // qSort思路，比pivot大的全在pivot右手边，注意还有一个条件是要一直保证left < right
            while(left < right && pivot <= arr[right]) {
                right --;
            }
          //退出上面的while循环是因为我们发现了pivot右边有比pivot小的
          //大胆交换，因为我们已经备份了第一个元素即pivot，下面左边同理
            arr[left] = arr[right];
            while(left < right && arr[left] <= pivot) {
                left ++;
            }
            arr[right] = arr[left];
        }
       //退出的条件是left == right，所以这个位置就是我们之前备份的pivot的位置，之后恢复好后返回下标即可
        arr[left] = pivot;
        return left;
    }
}