我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?
当前回答
还有一种算法,比快速选择算法性能更好。它叫做弗洛伊德-铆钉(FR)算法。
原文:https://doi.org/10.1145/360680.360694
下载版本:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf
维基百科文章https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
我尝试在c++中实现快速选择和FR算法。我还将它们与标准c++库实现std::nth_element(基本上是quickselect和heapselect的introselect混合)进行了比较。结果是快速选择和nth_element的平均运行,而FR算法的平均运行约。速度是它们的两倍。
我用于FR算法的示例代码:
template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
if (n == 0)
return *(std::min_element(data.begin(), data.end()));
else if (n == data.size() - 1)
return *(std::max_element(data.begin(), data.end()));
else
return _FRselect(data, 0, data.size() - 1, n);
}
template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
size_t leftIdx = left;
size_t rightIdx = right;
while (rightIdx > leftIdx)
{
if (rightIdx - leftIdx > 600)
{
size_t range = rightIdx - leftIdx + 1;
long long i = n - (long long)leftIdx + 1;
long long z = log(range);
long long s = 0.5 * exp(2 * z / 3);
long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);
size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);
_FRselect(data, newLeft, newRight, n);
}
T t = data[n];
size_t i = leftIdx;
size_t j = rightIdx;
// arrange pivot and right index
std::swap(data[leftIdx], data[n]);
if (data[rightIdx] > t)
std::swap(data[rightIdx], data[leftIdx]);
while (i < j)
{
std::swap(data[i], data[j]);
++i; --j;
while (data[i] < t) ++i;
while (data[j] > t) --j;
}
if (data[leftIdx] == t)
std::swap(data[leftIdx], data[j]);
else
{
++j;
std::swap(data[j], data[rightIdx]);
}
// adjust left and right towards the boundaries of the subset
// containing the (k - left + 1)th smallest element
if (j <= n)
leftIdx = j + 1;
if (n <= j)
rightIdx = j - 1;
}
return data[leftIdx];
}
template <typename T>
int sgn(T val) {
return (T(0) < val) - (val < T(0));
}
其他回答
虽然不是很确定O(n)复杂度,但肯定在O(n)和nLog(n)之间。也肯定更接近于O(n)而不是nLog(n)函数是用Java编写的
public int quickSelect(ArrayList<Integer>list, int nthSmallest){
//Choose random number in range of 0 to array length
Random random = new Random();
//This will give random number which is not greater than length - 1
int pivotIndex = random.nextInt(list.size() - 1);
int pivot = list.get(pivotIndex);
ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();
//Split list into two.
//Value smaller than pivot should go to smallerNumberList
//Value greater than pivot should go to greaterNumberList
//Do nothing for value which is equal to pivot
for(int i=0; i<list.size(); i++){
if(list.get(i)<pivot){
smallerNumberList.add(list.get(i));
}
else if(list.get(i)>pivot){
greaterNumberList.add(list.get(i));
}
else{
//Do nothing
}
}
//If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
if(nthSmallest < smallerNumberList.size()){
return quickSelect(smallerNumberList, nthSmallest);
}
//If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
//The step is bit tricky. If confusing, please see the above loop once again for clarification.
else if(nthSmallest > (list.size() - greaterNumberList.size())){
//nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in
//smallerNumberList
nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
return quickSelect(greaterNumberList,nthSmallest);
}
else{
return pivot;
}
}
你确实喜欢快速排序。随机选择一个元素,然后将所有元素推高或推低。此时,您将知道您实际选择了哪个元素,如果它是第k个元素,您就完成了,否则您将重复bin(更高或更低),第k个元素将落在其中。从统计学上讲,找到第k个元素所需的时间随着n, O(n)而增加。
下面是完整实现的链接,其中相当广泛地解释了在无序算法中查找第k个元素的算法是如何工作的。基本思想是像快速排序一样对数组进行分区。但为了避免极端情况(例如每一步都选择最小的元素作为主元,使算法运行时间退化为O(n^2)),采用特殊的主元选择,称为中位数的中位数算法。在最坏情况和平均情况下,整个解在O(n)时间内运行。
这里是全文的链接(它是关于寻找第k个最小的元素,但寻找第k个最大的元素的原理是相同的):
在无序数组中寻找第k个最小元素
根据本文,在n个项目的列表中寻找第k个最大的项目,下面的算法在最坏的情况下将花费O(n)时间。
将数组分成n/5个列表,每个列表有5个元素。 求每个5个元素的子数组的中值。 递归地找到所有中位数的中位数,记作M 将数组划分为两个子数组第一个子数组包含大于M的元素,设这个子数组为a1,而其他子数组包含小于M的元素,设这个子数组为a2。 如果k <= |a1|,返回选择(a1,k)。 k−1 = |a1|,返回M。 如果k> |a1| + 1,返回选择(a2,k−a1−1)。
分析:如原文所述:
我们使用中位数将列表分成两部分(前一半, 如果k <= n/2,反之则为后半部分)。这个算法需要 对于某个常数c,递归第一级的时间cn/2 at 下一层(因为我们在大小为n/2的列表中递归),cn/4在 第三层,以此类推。总时间为cn + cn/2 + cn/4 + .... = 2cn = o(n)。
为什么分区大小是5而不是3?
如原文所述:
将列表除以5可以保证最坏情况下70−30的分割。至少 至少一半的中位数大于中位数的中位数 n/5块中的一半至少有3个元素,这就给出了a 3n/10的分割,这意味着另一个分区在最坏情况下是7n/10。 得到T(n) = T(n/5)+T(7n/10)+O(n)由于n/5+7n/10 < 1 最差情况运行时间isO(n)。
现在我尝试将上述算法实现为:
public static int findKthLargestUsingMedian(Integer[] array, int k) {
// Step 1: Divide the list into n/5 lists of 5 element each.
int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
// Step 2: Find pivotal element aka median of medians.
int medianOfMedian = findMedianOfMedians(array, noOfRequiredLists);
//Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
for (Integer element : array) {
if (element < medianOfMedian) {
listWithSmallerNumbers.add(element);
} else if (element > medianOfMedian) {
listWithGreaterNumbers.add(element);
}
}
// Next step.
if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
return -1;
}
public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
int[] medians = new int[noOfRequiredLists];
for (int count = 0; count < noOfRequiredLists; count++) {
int startOfPartialArray = 5 * count;
int endOfPartialArray = startOfPartialArray + 5;
Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
// Step 2: Find median of each of these sublists.
int medianIndex = partialArray.length/2;
medians[count] = partialArray[medianIndex];
}
// Step 3: Find median of the medians.
return medians[medians.length / 2];
}
为了完成,另一种算法利用优先队列,花费时间O(nlogn)。
public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
int p = 0;
int numElements = nums.length;
// create priority queue where all the elements of nums will be stored
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// place all the elements of the array to this priority queue
for (int n : nums) {
pq.add(n);
}
// extract the kth largest element
while (numElements - k + 1 > 0) {
p = pq.poll();
k++;
}
return p;
}
这两个算法都可以被测试为:
public static void main(String[] args) throws IOException {
Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
System.out.println(findKthLargestUsingMedian(numbers, 8));
System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
}
如预期输出为: 18 18
遍历列表。如果当前值大于存储的最大值,则将其存储为最大值,并将1-4向下碰撞,5从列表中删除。如果不是,将它与第2条进行比较,然后做同样的事情。重复,检查所有5个存储值。应该是O(n)