【数据结构与算法】选择算法 selection

本文主要是介绍【数据结构与算法】选择算法 selection，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

选择算法指的是解决选出序列中第n大的元素。比如中位数。

方法如下：

1.使用priorityqueue，维持size为k，如果queue的size小于k，则直接加入，否则看最小的元素能否比得过，比得过就剔除最小元素，加入新元素，比不过就看后面的元素，最后返回堆顶元素即可。这里需要使用最小堆。

 

public int findKthMax(int[] array, int k){PriorityQueue<Integer> minHeap = new PriorityQueue<>();for(int i : array){if(minHeap.size() < k)minHeap.add(i);else if(minHeap.peek() < i){minHeap.poll();minHeap.add(i);}}return minHeap.peek();}

 

2.快速选择，使用了快排中的partition思想，每一次划分都是On复杂度。思路是选择一个轴元素pivot，把数组做一次划分，pivot左边都是小的等于pivot的，右边是大于pivot的，然后看pivot的位置，如果就是a.length - k，说明，pivot右侧有k-1个元素，那么pivot就是第k大的元素，否则如果位置小于a.length - k，那么应该在左半边寻找，否则在右半边寻找。

写这个算法有一个小技巧，在初始化的时候就直接把第k大转换成数组的索引位置，后面的所有比较都是基于索引位置的而不是第几大，写起来更简单。

这个算法的最坏复杂度是On2，每一次都恰好分为了个数为1的一组。最好是Onlogn。《算法导论》中指出，如果采用随机算法，即partition的pivot是随机选择的，那么平均复杂度是Onlogn，注意这是平均，最坏仍然是On2。

那么如何实现随机化的partition，很简单，原本我们是默认选第一个元素为pivot的，这时只需要随机选一个元素作为第一个元素即可，即先做一次随机的交换。

代码：

public int findKthLargest(int[] nums, int k) {return findKthSmallest(nums, nums.length - k, 0, nums.length - 1);}public int findKthSmallest(int[] nums, int k, int start, int end) {if (start > end) {return -1;}int index = partition(nums, start, end);if (index == k){return nums[index];} else if (index < k) {return findKthSmallest(nums, k, index + 1, end);} else {return findKthSmallest(nums, k, start, index - 1);}}private int partition(int[] nums, int start, int end){if (start > end){return -1;}int pivot = nums[start];int last = start;for (int i = start + 1; i <= end; i++) {if (nums[i] <= pivot) {swap(nums, i, ++last);}}swap(nums, start, last);return last;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

 

3. BFPTR算法，该名称来自五个发明者的名字，是对上述快速选择的改进，主要是对最差情况的改进，优化pivot的选择。可以证明最差是On。

 

（1）先把array分为每组包含5个元素的组，最后一组可能不满；找出每一组的中位数，并且移动至array的前面，方便后续寻找；这一步是特殊的case，用一个插入排序就可以实现。

（2）找出中位数的中位数，这一步是一次递归地调用；

（3）得到pivot以后，按照pivot来partition；然后分3个case，类似于快速选择。

下面是一些别人的实现：

http://noalgo.info/466.html

时间复杂度分析：（1）步需要On；（2）步需要T（n/5）；（3）考虑最坏情况，那么就是没有找到，需要递归到高位或者地位去寻找，相当于递归调用了一次BFPTR算法。那么我们需要得到递归地元素个数。假设中位数的中位数是x，那么有一半的组中，至少含有3个元素大于x，即1/2 * n/5 * 3 = 3/10 * n。那么至多有n-3/10 * n = 7/10 * n 元素是大于x的。同理至多有7/10 * n小于x的。因此这一步至多需要T（7/10*n）。要注意，这里中位数的中位数并不是中位数，所以不是2/n，即一分为二。那么，总的复杂度是On。可以把上述式子展开等比数列计算，或者使用主定理。

 

 

这篇关于【数据结构与算法】选择算法 selection的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---