Algorithmus, der die N-te häufigste Zahl im Array findet

Question

Ich möchte einen Algorithmus schreiben, der die n-te häufigste Zahl in einem Array findet. Ich habe eine Lösung, aber nicht optimal (Testnummern habe ich bereits getestet) Ich frage mich, ob es eine optimale Lösung gibt? Hier ist meine Lösung:

most_freq_element(a,n){ 
final_cnt = 0, curr_cnt = 1, final_freq_num = -1, curr_freq_num = -1; 
for(i = 0; i < n-1; i++) 
{ 
    if (a[i]!=-1){ 
     curr_freq_num = a[i]; 
     for(j =i+1; j < n; j++){ 
      if(curr_freq_num == a[j] && final_freq_num != curr_freq_num){ 
       curr_cnt++; 
      } 
     } 
     if(final_cnt < curr_cnt){ 
      final_cnt = curr_cnt; 
      curr_cnt = 1; 
      final_freq_num = curr_freq_num; 
     } 
    } 
} 
printf("Num = %d and times = %d", final_freq_num, final_cnt); 
} 



nth_most_frequent_element(a,n,k){  
if(k==1){ 
    return most_freq_element(a,n); 
} 
else{ 
    for (i=0;i<k;i++){ 
     int most_freq_num = most_freq_element(a,n); 

     for(i = 0; i < n-1; i++){ 
      if (a[i]==most_freq_num){ 
       a[i]=-1; 
      } 
     } 
    } 
    return most_freq_element(a,n); 
} 
} 

Answer 1

Wie wäre das? Am schlimmsten ist die Komplexität O (2.N.logN + k.min (k, d)), d: Anzahl der eindeutigen Werte in einem

most_freq_element(a[0..n-1],n,k) 
{ 
    count[0..k], value[0..k]; // k + 1 elements 
    i, j, l; 

    qsort(a, n) 

    j = 0; 
    l = 0; 
    value[0] = a[0]; 
    count[0] = 1; 
    for (i = 1; i < n; ++i) 
    { 
    if (a[i] != value[j]) 
    { 
     if (++l > k) l = k; 
     j = l; 
     value[j] = a[i]; 
     count[j] = 0; 
    } 

    ++count[j]; 

    while (j > 0 && count[j] > count[j - 1]) 
    { 
     swap(count[j], count[j - 1]); 
     swap(value[j], value[j - 1]); 
     --j; 
    } 
    } 
    printf("Num = %d and times = %d", value[k - 1], count[k - 1]); 
} 

Answer 2

würde ich wahrscheinlich eine hashmap/table machen, und jeder Wert erhöht auf Kollision, so dass die Zahl der Schlüssel ist und der Wert die Anzahl der Kollisionen ist. Dann, wenn Sie fertig sind, aggregieren Sie es zu einer sortierten Liste und greifen Sie das n-te Element. Würde in O (n) laufen, was ziemlich optimal ist.

Edit: Eigentlich würde die Sortierung n * log (n) kosten.