我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?
当前回答
创建优先级队列。 将所有元素插入堆中。 调用poll() k次。 getKthLargestElements(int[] arr) { PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> (y-x)); //将所有元素插入堆中 For (int ele: arr) pq.offer(避署); //调用poll() k次 int i = 0; 而(i< k) { Int result = pq.poll(); } 返回结果; }
其他回答
我提出了这个算法,似乎是O(n):
假设k=3我们想找出数组中第三大的元素。我将创建三个变量,并将数组中的每一项与这三个变量中的最小值进行比较。如果数组item大于最小值,则用item的值替换最小值变量。我们继续做同样的事情,直到数组结束。三个变量中的最小值是数组中第三大的项。
define variables a=0, b=0, c=0
iterate through the array items
find minimum a,b,c
if item > min then replace the min variable with item value
continue until end of array
the minimum of a,b,c is our answer
为了找到第K大的项,我们需要K个变量。
例如:(k = 3)
[1,2,4,1,7,3,9,5,6,2,9,8]
Final variable values:
a=7 (answer)
b=8
c=9
有人可以审查这个,让我知道我错过了什么?
function nthMax(arr, nth = 1, maxNumber = Infinity) {
let large = -Infinity;
for(e of arr) {
if(e > large && e < maxNumber ) {
large = e;
} else if (maxNumber == large) {
nth++;
}
}
return nth==0 ? maxNumber: nthMax(arr, nth-1, large);
}
let array = [11,12,12,34,23,34];
let secondlargest = nthMax(array, 1);
console.log("Number:", secondlargest);
它类似于快速排序策略,在快速排序策略中,我们选择一个任意的枢轴,并将较小的元素放在它的左边,将较大的元素放在右边
public static int kthElInUnsortedList(List<int> list, int k)
{
if (list.Count == 1)
return list[0];
List<int> left = new List<int>();
List<int> right = new List<int>();
int pivotIndex = list.Count / 2;
int pivot = list[pivotIndex]; //arbitrary
for (int i = 0; i < list.Count && i != pivotIndex; i++)
{
int currentEl = list[i];
if (currentEl < pivot)
left.Add(currentEl);
else
right.Add(currentEl);
}
if (k == left.Count + 1)
return pivot;
if (left.Count < k)
return kthElInUnsortedList(right, k - left.Count - 1);
else
return kthElInUnsortedList(left, k);
}
在线性时间内找到数组的中值,然后使用与快速排序完全相同的划分程序将数组分为两部分,中值左边的值小于(<)中值,右边的值大于(>)中值,这也可以在线性时间内完成,现在,找到数组中第k个元素所在的部分, 现在递归式变成: T(n) = T(n/2) + cn 得到O (n) /。
根据本文,在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