Quel est le moyen le plus rapide de trouver le Nième plus grand nombre d'un tableau INT?

Question

Je veux une fonction plus rapide pour trouver le Nème plus grand nombre d'un tableau Int en C #. Cette fonction prend N et Array et retourne l' index de ce nombre.

Voici ce que j'ai déjà. Il trie simplement le tableau puis retourne l'index de ce nombre. Cela fonctionne parfaitement mais je ne sais pas si c'est le moyen le plus rapide. il semble logique d'être un algorithme sans tri complet.

 static int myFunction(int[] array, int N){
    int[] indexes = new int[array.Length];
    for (int i = 0; i < indexes.Length; i++)
        indexes[i] = i;

    for (int i = 0; i < array.Length; i++)
    {
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[i] < array[j])
            {
                int m = array[j];
                array[j] = array[i];
                array[i] = m;

                m = indexes[j];
                indexes[j] = indexes[i];
                indexes[i] = m;
            }
        }
    }
    return indexes[N];
}
 

quelques résultats:

 myFunction(new int[] { 1, 3, 2, 0, 10 }, 0); //returns 4 (index of 10)
myFunction(new int[] { 1, 3, 2, 0, 10 }, 1); //returns 1 (index of 3)
myFunction(new int[] { 1, 3, 2, 0, 10 }, 2); //returns 2 (index of 2)
 

Answer 1

L'algorithme de sélection rapide aléatoire fonctionne dans la complexité de cas moyenne O (n). Pratiquement, il est très rare d'être O (n ^ 2). Il utilise la fonction de partition de quicksort

Answer 2

Si votre tableau a une taille d'un tas de chiffres et vous avez besoin de la cinquième plus grand nombre, alors vous êtes de tri beaucoup de numéros que vous n'aurez pas besoin.

Ne serait-il pas plus rapide de garder un ascendant triée séquence de longueur n (liste chaînée?), et pour chaque élément vérifier si il est plus grand que le premier (qui est le plus petit dans l'ordre croissant

• Si les plus petites: passez à l'élément suivant dans votre grand tableau
• Si la plus grande: suppression de la plus petite à partir de votre tableau trié qui est le premier élément et l'insérer le plus grand élément dans l'endroit approprié, tenir le tableau trié.

Après avoir scanné votre tableau, le premier élément dans votre séquence triée est celui que vous recherchez.

La plupart des comparaisons n'y a que le premier élément de ton tableau trié. Vous aurez à modifier le tableau N-fois, une fois pour les N plus grands nombres. Un changement de la matrice est de supprimer le premier élément (le plus petit) et trouver l'endroit où insérer le nouvel élément à garder le tableau trié

Correction: mon relevé de compte que le tableau doit être modifié N-heure est incorrect. Ceci peut être vu plus facilement en proposant un tableau trié dans l'ordre croissant: par rapport à chaque numéro sera plus grand que le plus petit dans le N-tableau de taille, et ainsi provoquer une remplacer la

Answer 3

Ce serait la mise en œuvre de la réponse de @ HaraldDutch.

 int get(int[] array, int n)
{
    var comparer = Comparer<int>.Create((x, y) => array[x].CompareTo(array[y]));    //compare the array entries, not the indices
    var highestIndices = new SortedSet<int>(comparer);
    for (var i = 0; i < array.Length; i++)
    {
        var entry = array[i];
        if (highestIndices.Count < n) highestIndices.Add(i);
        else if (array[highestIndices.Min] < entry)
        {
            highestIndices.Remove(highestIndices.Min);
            highestIndices.Add(i);
        }
    }

    return highestIndices.Min;
}
 

Vous devez cependant passer 1 au lieu de 0.

Answer 4

vous devez utiliser l'algorithme de sélection https://en.wikipedia.org/wiki/Selection_algorithm

ici de belles diapositives: https://c3p0demo.googlecode.com/svn/trunk/scalaDemo/script/Order_statistics.ppt généralement l'algorithme:

 Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group's median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)
 

Answer 5

Vous pouvez créer un tas de taille N qui a le plus grand nombre comme premier élément (par opposition à la plus petite habituellement donnée). Ensuite, vous marchez par le biais de votre tableau d'entiers, et chaque fois que vous avez un élément plus petit que le plus grand membre de la tas, vous l'insérez dans le tas. Si ça fait des tas de dépasser une taille de N, vous devez supprimer le plus grand membre en elle.

Que devrait être l'un des moins chers de façons de le faire. Spécifique "n-ième plus grande de m" algorithmes peuvent le battre, mais probablement pas à l'infini.