java - 如何在 QuickSelect 中实现重复
问题描述
我做了快速选择算法,就是在一个数组中找到第k个最小的数。我的问题是,它只适用于没有重复的数组。如果我有一个数组
arr = {1,2,2,3,5,5,8,2,4,8,8}
它会说第三小的数字是 2,但实际上是 3。
我被困在做什么,这是我的两个方法 quickSelect 和 Partition:
private int quickselect(int[] array, int leftIndex, int rightIndex, int kthSmallest) {
if(kthSmallest > array.length - 1){
System.out.print("Number does not exist. Please enter a number less than: ");
return array.length - 1;
}
if (leftIndex == rightIndex) {
return array[leftIndex];
}
int indexOfPivot = generatePivot(leftIndex, rightIndex);
indexOfPivot = quickSelectPartition(array, leftIndex, rightIndex, indexOfPivot);
if (kthSmallest == indexOfPivot) {
return array[kthSmallest];
} else if (kthSmallest < indexOfPivot) {
return quickselect(array, leftIndex, indexOfPivot - 1, kthSmallest);
} else {
return quickselect(array, indexOfPivot + 1, rightIndex, kthSmallest);
}
}
private int quickSelectPartition(int[] array, int left, int right, int pivotIndex) {
int pivotValue = array[pivotIndex];
swapIndexes(array, pivotIndex, right);
int firstPointer = left;
for(int secondPointer = left; secondPointer < right; secondPointer++) {
if(array[secondPointer] < pivotValue) {
swapIndexes(array, firstPointer, secondPointer);
firstPointer++;
}
}
swapIndexes(array, right, firstPointer);
return firstPointer;
}
解决方案
如果增加运行时间是可以接受的,您可以首先将不同的元素复制到一个新数组中:
private int[] getDistinct(int[] array) {
Set<Integer> distinct = new HashSet<>();
int endIdx = 0;
for (int element : array) {
if (distinct.add(element)) {
array[endIdx++] = element;
}
}
return Arrays.copyOfRange(array, 0, endIdx);
}
然后对此进行快速选择:
int[] arr = new int[] {1, 2, 2, 3, 5, 5, 8, 2, 4, 8, 8};
int kthSmallest = 6;
int[] distinctArray = getDistinct(arr);
int kthSmallestElement = quickselect(distinctArray, 0, distinctArray.length - 1, kthSmallest - 1);
System.out.println(kthSmallestElement);
输出:
8
推荐阅读
- python - Django 错误 -django.db.utils.DataError: value too long for type character varying(1)
- android - 应用被多个 Firebase 项目杀死时未收到 FCM 通知
- c# - C# 从同一命名空间中的单独类调用辅助函数,没有前缀并且可以访问 System.Web.UI.Page
- sql - 根据我想对多个值进行 CASE 的聚合行生成一个值?
- python - 在日期时间段内分配累积的第 N 天。[即这一行属于第134天]
- assembly - 为什么堆栈中地址的大小大于保存的eip地址的大小?
- javascript - 为什么事件“transitionend”会触发两次?
- javascript - 如果'React'是'react'的默认导出,为什么我们不能使用其他名称而不是'React'
- javascript - 项目从 Babel 6 迁移到 Babel 7 -> 错误导入/导出不在顶层
- python - 使用多处理创建同一进程的多个实例