我有一个包含唯一元素的数组。我需要以尽可能最低的复杂度找出数组中的前 n 个最大元素。到目前为止我能想到的解决方案的复杂度为 O(n^2)。
int A[]={1,2,3,8,7,5,3,4,6};
int max=0;
int i,j;
int B[4]={0,0,0,0,};//where n=4;
for(i=0;i<A.length();i++)
{
if(A[i]>max)
max=A[i];
}
B[0]=max;
for(i=1;i<n;i++){
max=0;
for(j=0;j<A.length();j++){
if(A[j]>max&&A[j]<B[i-1])
max=A[j];
}
B[i]=max;
}
如果有人能提出一个复杂性更低的更好的解决方案，我将不胜感激。而且我不打算改变原来的数组！！
使用选择算法找到第k大元素。
接下来，迭代数组并找到大于/等于它的所有元素。
复杂度：选择为O(n)，迭代为O(n)，所以总和也是O(n)
选择 n 最大元素的常用技巧是维护最小优先级队列。
总复杂度：O(N log n)，其中 N 是数组中元素的总数。
我将实现细节留给您作为练习（第一步是了解优先级队列，并实现一个）。
如果您的元素是 i 到 k（含 k >= i）范围内的整数（或任何整数类型），则可以在 O(n) 中完成此操作。有了这个约束，你就可以对此应用“桶排序”。
这个想法很简单。分配 k - i + 1 个桶。现在，迭代您的集合并增加该整数的存储桶。然后，最后，您可以通过创建找到的尽可能多的整数（即存储桶编号）来“重新创建”排序列表。
例如，
int collection[] = { 10, 4, 7, 1, 9, 0, 12 }; // maximum value to expect is 12, minimum is 0
int buckets[ 13 ] = { 0 };
for( int i = 0; i < 13; i++ )
{
int n = collection[ i ];
buckets[ n ]++;
}
// the first n largest elements (n = 4)
for( int j = 12; j >= 12 - 4; j-- )
{
int n = buckets[ j ];
while( n > 0 )
{
printf( "%d ", j );
n--;
}
}
printf( "\n" );
使用快速排序的修改版本。您不需要实际对整个数组进行排序。只需要划分大于主元值的 N 个元素即可。欲了解更多信息，请阅读算法简介。
您可以使用使用堆（maxHeap）的优先级队列来解决这个问题。执行堆 n 次以获得前 n 个最大的元素。每个堆操作需要 O(log N) 时间，因此 N 堆操作将导致 O(N log N) 时间。
我不相信这一点，但你也可以在 O(n) 中创建一个堆。然后删除根 k 次并堆化堆以获得 k 个最大的数字。 这样，对于每个最大的数字，您将花费 log(n)。
public class HeapSort1{
public static void main(String args[]){
int[] array={5,75,1,5,4,1,2,4,8,4,2,15,4,2,1,5,779,9,1};
int heapsize=array.length-1;
for(int i=heapsize/2;i>=0;i--){
maxHeapify(array,i,heapsize);
}
for(int i=heapsize;i>0;i--){
array[i]=array[0]+array[i];
array[0]=array[i]-array[0];
array[i]=array[i]-array[0];
maxHeapify(array,0,--heapsize);
}
printArray(array);
}
public static void maxHeapify(int[] array,int i,int heapsize){
int largest=i;
int left=2*i+1;
int right=2*i+2;
if(left<=heapsize && array[left]>array[i]){
largest=left;
}
if(right<=heapsize && array[right]>array[largest]){
largest=right;
}
if(largest!=i){
array[i]=array[largest]+array[i];
array[largest]=array[i]-array[largest];
array[i]=array[i]-array[largest];
maxHeapify(array,largest,heapsize);
}
}
public static void printArray(int[] array){
System.out.print("\n [");
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
System.out.print("] \n");
}
public static int getMax(){
int max=array[0];
array[0]=array[heapsize];
maxHeapify(array,0,--heapsize);
}
}
我按照@Alexandre C 尝试了这个。
这将获取无界输入的前 10 项。它在处理输入中的 20 个项目后中断。
import random
import time
top_10_items = []
cnt = 1
while True:
rand = random.randint(1,100)
print(rand)
time.sleep(1)
if len(top_10_items) !=10:
top_10_items.append(rand)
else:
m = min(top_10_items)
if rand > m:
top_10_items.append(rand)
top_10_items.remove(m)
print(top_10_items)
cnt+=1
if cnt==20:
break
//First we sort the array in descending order and after the array
//is sorted, we print the number of largest elements we want
import java.util.Scanner;
class bubble_sort{
static void buuble_sort(int[] array,int n){
int temp=0;
//I have sorted this array using bubble sorting technique, in case you don't know, you must know, it's effective, easy and fast.
for (int i=0; i<n;++i){
for (int j=0;j<n-1;j++){
if (array[j]<array[j+1]){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
//this method print the number of 'n' largest we want.
static void print_sort(int array[],int num){
for (int i=0;i<num;++i){
System.out.print(array[i]+" ");
}
}
public static void main(String[] args)
{
Scanner obj=new Scanner(System.in);
int[] array={12, 34, 56, 32, 45, 22,3, 18};
int n=array.length;
System.out.println("the elements of the array are as follows:-");
for (int i=0; i<array.length;++i){
System.out.print(array[i]+" ");
}
buuble_sort(array,n);
System.out.print("\nEnter the number of largest elements you want from the above array : ");
//give the integer input as 'n' number of largest elements.
int num=obj.nextInt();
print_sort(array,num);
}
}
//finding the bigest number in the array//
double big = x[0];
for(t=0;t<x[t];t++)
{
if(x[t]>big)
{
big=x[t];
}
}
printf("\nThe bigest number is %0.2lf \n",big);