查找数组中的前n个最大元素
我有一个包含唯一元素的数组。 我需要以尽可能最小的复杂性找出数组中的前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;imax) max=A[i]; } B[0]=max; for(i=1;i<n;i++){ max=0; for(j=0;jmax&&A[j]<B[i-1]) max=A[j]; } B[i]=max; } 如果有人能想出一个更复杂的更好的解决方案，我将非常感激。 而且我不打算改变原来的arrays！
使用选择算法找到第k个最大元素。
接下来，迭代数组并找到所有大于/等于它的元素。
复杂度： O（n）用于选择，O（n）用于迭代，因此总数也是O（n）
选择n个最大元素的常用技巧是维护最小优先级队列。
- 无条件地将n个第一个元素插入队列
- 对于每个剩余元素x，如果它大于队列的最小元素（O（log n）操作），则插入x，并删除最小元素（O（log n））。
- 完成后，优先级队列包含n个元素，这些元素是原始数组的n个最大元素。
总复杂度：O（N log n）其中N是数组中元素的总数。
我将练习详细信息留给您（第一步是了解优先级队列，并实现一个）。
如果元素是一个范围内的整数（或任何整数类型），则可以在O（n）中执行此操作，i到k包括k> = i。 使用此约束，您可以对此应用“桶排序”。
这个想法很简单。 分配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" );
使用Quick Sort的修改版本。 您不需要对整个数组进行实际排序。 您只需要分割大于枢轴值的N个元素。 有关更多信息，请阅读算法简介。
您可以使用Heap（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
我根据@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
//finding the bigest number in the array// double big = x[0]; for(t=0;tbig) { big=x[t]; } } printf("\nThe bigest number is %0.2lf \n",big);