中国建设银行江西分行网站首页,免费域名分发系统,wordpress伪装帝国cms,wordpress标签生成目录 1.概述2.代码实现2.1.基于简单交换排序2.2.基于堆排序2.3.基于快速排序 3.应用 更多数据结构与算法的相关知识可以查看数据结构与算法这一专栏。 1.概述
#xff08;1#xff09;快速选择算法 (Quick Select Algorithm) 是一种用于在无序数组中寻找第 k 小#xff08;… 目录 1.概述2.代码实现2.1.基于简单交换排序2.2.基于堆排序2.3.基于快速排序 3.应用 更多数据结构与算法的相关知识可以查看数据结构与算法这一专栏。 1.概述
1快速选择算法 (Quick Select Algorithm) 是一种用于在无序数组中寻找第 k 小或第 k 大元素的高效算法它是快速排序算法的一个变种。快速选择算法的基本思想是通过每次选取一个枢纽元素通常是随机选择或者选择第一个或最后一个元素将数组划分为两个部分并将枢纽元素放置在其最终的排序位置上。然后根据枢纽元素的位置判断第 k 小或第 k 大元素在数组的左半部分还是右半部分并且递归地在相应的部分中查找。
2与快速排序不同的是快速选择算法只需要递归处理数组的一半。这样在平均情况下算法的时间复杂度为 O(n)其中 n 是数组的大小。然而在最坏情况下快速选择算法的时间复杂度可能达到 O(n2)但这种情况的概率很低。
2.代码实现
实现快速选择算法有许多方式下面将逐一介绍。需要注意的是在下面的实现方式中只有基于快速排序的快速选择算法的时间复杂度为 O(n)。此外有关排序算法的具体知识可以参考【算法】内部排序这篇文章。 注意下面的代码实现都是找出数组中的第 k 个最大元素。 2.1.基于简单交换排序
这里考虑利用简单交换排序的特点即每完成一趟排序就至少会有一个元素的位置确定那么只需要对数组 nums 进行 k 躺降序排序此时的 nums[k - 1] 必为数组 nums 中第 k 个最大的元素将其返回即可。该算法的时间复杂度为 O(k * n)具体实现代码如下
class Solution {public int findKthLargest(int[] nums, int k) {//进行 k 趟排序for (int i 0; i k; i) {for (int j i 1; j nums.length; j) {if (nums[i] nums[j]) {//交换 nums[i] 和 nums[j]int tmp nums[i];nums[i] nums[j];nums[j] tmp;}}}return nums[k - 1];}
}2.2.基于堆排序
我们可以使用堆排序来找出数组中的第 k 个最大元素即建立一个大根堆做 k − 1 次删除操作后堆顶元素就是我们要找的答案。在 Java 中我们可以直接使用优先级队列来完成这一操作。当然如果想更加了解推排序我们也可以手动实现。该算法的时间复杂度为 O(nlogk)具体代码如下
//使用优先级队列
class Solution {public int findKthLargest(int[] nums, int k) {//创建一个大根堆PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a);//将数组中的元素加入堆for (int num : nums) {maxHeap.offer(num);}//进行 k - 1 次删除操作for (int i 0; i k - 1; i) {maxHeap.poll();}//堆顶元素就是第 k 个最大元素return maxHeap.peek();}
}//手动实现堆排序
class Solution {public int findKthLargest(int[] nums, int k) {int length nums.length;//循环建立初始堆调用 sift 算法 ⌊n / 2⌋ 次for (int i (length - 1) / 2; i 0; i--) {sift(nums, i, length - 1);}for (int i length - 1; i length - k; i--) {//将 nums[i] 与根 nums[0] 交换int tmp nums[0];nums[0] nums[i];nums[i] tmp;//对 nums[0...i - 1] 进行筛选得到 i 个节点的堆sift(nums, 0, i - 1);}return nums[length - k];}//对 nums[low...high] 进行筛选使得以 nums[low] 为根节点的左子树和右子树均为大根堆public void sift(int[] nums, int low, int high) {// nums[j] 是 nums[i] 的左孩子int i low;int j (i 0) ? 1 : 2 * i;int tmp nums[i];while (j high) {//如果右孩子更大则将 j 指向右孩子if (j high nums[j] nums[j 1]) {j;}//根节点小于最大孩子节点if (tmp nums[j]) {nums[i] nums[j];nums[j] tmp;i j;j 2 * i;} else {//如果跟节点大于等于最大孩子关键字筛选结束break;}}}
}2.3.基于快速排序
具体实现思路如下
首先定义一个函数 findKthLargest该函数接收一个数组 nums 和一个整数 k返回该数组中第 k 大的元素。在 findKthLargest 函数中调用 quickSelect 函数进行快速选择在数组 nums 的下标范围 [left, right] 中查找第 index 大的元素。在 quickSelect 函数中首先调用 randomPartition 函数进行随机划分得到基准元素的下标 q 判断 q 是否等于 index如果相等则说明已经找到了第 k 大的元素直接返回 nums[q]。如果 q 不等于 index根据 q 在 [left, right] 中与 index 的大小关系递归调用 quickSelect 函数查找第 k 大的元素。如果 q index则第 k 大的元素在右区间递归调用 quickSelect(nums, q 1, right, index)否则第 k 大的元素在左区间递归调用 quickSelect(nums, left, q - 1, index)。 randomPartition 函数采用随机选择基准元素的方法将一个下标 i 转换成基准元素使得 [left,i-1] 中的所有元素都小于等于基准元素[i1, right] 中的所有元素都大于等于基准元素并返回基准元素的下标。partition 函数是快速排序中划分数组的核心操作它以 nums[left] 为基准将数组 nums[left…right] 划分为两个子数组 nums[left…i-1] 和 nums[i1…right]并返回最终元素 nums[left] 所在的下标 i。此处实现的是双指针的快速排序实现方式。
class Solution {Random random new Random();public int findKthLargest(int[] nums, int k) {//第 K 个最大元素其实就是升序排序后的元素 nums[nums.length - k]return quickSelect(nums, 0, nums.length - 1, nums.length - k);}public int quickSelect(int[] nums, int left, int right, int index) {int q randomPartition(nums, left, right);if (q index) {//当前划分的下标 q 等于 index则说明这次划分操作后已经找到了第 k 个最大元素其下标为 q直接返回 nums[q] 即可return nums[q];} else {/*当前划分的下标 q 不等于 index: (1) 如果 q index那么则说明第 k 个最大元素在右区间此时递归右区间(2) 如果 q index那么则说明第 k 个最大元素在左区间此时递归左区间*/if (q index) {return quickSelect(nums, q 1, right, index)} else {return quickSelect(nums, left, q - 1, index);}}}public int randomPartition(int[] nums, int left, int right) {// random.nextInt(int num): 随机返回一个 [0, num) 内的整数int i random.nextInt(right - left 1) left;int tmp nums[i];nums[i] nums[left];nums[left] tmp;return partition(nums, left, right);}//以 nums[left] 为基准进行一趟划分并返回最终元素 nums[left] 所在的下标private int partition(int[] nums, int left, int right) {int i left, j right;//以 nums[left] 为基准int benchmark nums[left];while (i j) {//从右向左扫描找到一个小于 benchmark 的元素 nums[j]while (i j benchmark nums[j]) {j--;}nums[i] nums[j];//从左向右扫描找到一个大于 benchmark 的元素 nums[i]while (i j nums[i] benchmark) {i;}nums[j] nums[i];}nums[i] benchmark;return i;}
}3.应用
1快速选择算法在处理数组中第 k 大/小元素的问题上具有广泛的应用场景。以下是一些应用场景的示例
数组中的第 k 大/小元素快速选择算法可以在线性时间复杂度内找到数组中的第 k 大/小元素。这在需要找到排名靠前/靠后的元素时非常有用例如找到数组中的中位数或前 k 个最大的元素。排序问题在快速排序算法中使用快速选择算法找到基准元素的位置然后通过递归地对基准元素左右两部分进行排序最终实现对整个数组的排序。基于中位数的分割问题在一些分割问题中我们可以使用快速选择算法找到数组的中位数并将数组分割成两个部分。这在一些分治算法中非常常见例如快速排序、快速选择等。统计问题快速选择算法可用于解决一些统计问题例如找到数组中出现次数最多的元素、找到更大/更小的元素等。 总的来说快速选择算法适用于需要在数组中查找第 k 大/小元素的问题并且相比完全排序整个数组快速选择算法具有更高的效率。它在平均情况下的时间复杂度为O(n)在最坏情况下的时间复杂度为O(n2)但通过一些优化技巧可以将最坏情况下的时间复杂度降低到O(n)。 2例如在 462.最小操作次数使数组元素相等 II 这题中我们就可以使用快速选择算法来快速找出数组中的中位数并计算使所有数组元素相等需要的最小操作数。
