Comment trouver le k-ième plus petit entier dans un tableau non trié sans trier le tableau?

Je suis donc donné un (non triées) Un tableau de N entiers distincts, je suis en train de mettre en œuvre un divide-and-conquer algorithme pour trouver la k-ième plus petit élément (K ≤ N) de la matrice (c'est à dire qu'il serait l'ensemble de la plus petite si K=1). L'algorithme retourne la valeur de la k-ième plus petit élément dans le tableau. J'en ai besoin pour s'exécuter en O(N) fois dans la moyenne des cas. Quelqu'un pourrait-il me donner quelques conseils?

InformationsquelleAutor | 2011-02-16
  1. 13

    Sephy, je vais marcher à travers de très près. Vous devez toujours être prudent lorsque vous aider les gens avec des algorithmes, car, et je ne peux pas insister assez sur ce, algorithme de résolution de problèmes problèmes sont à des programmeurs de ce poids de levage est pour les athlètes professionnels. Savoir mettre vous-même dans le mode de penser comme un ordinateur est ce que vous aurez payé pour le faire dans quelques années. Donc, si les solutions sont donnés seulement à vous, vous allez être le gars qui rebondit de poste en poste tous les 6 mois au lieu de le gars qui devient le principal développeur, ou va sur son propre avec un succès de l'entreprise.

    Maintenant, que le délire est de la route...

    Traditionnellement, on pense à des algorithmes de parcourir le tableau une fois, et une boucle par elle différemment selon le premier résultat, et répétez jusqu'à ce que nous avons rencontré certaines conditions, à O(n^2). Les choses qui répondent à ce critère sont la sélection de tri, le tri par insertion, et de tri à bulles.

    Mais il n'a pas à être. Si nous pouvons diviser le tableau en segments et de prouver la taille de ces segments, nous pouvons garder sur un faible.

    Et, avec plus de diviser et conquérir des algorithmes, on peut commencer par le milieu.

    Let A be an array of size N with N distinct elements in it.

Let M be the element that resides at A[N/2]

Let A-large be an array of all elements greater than M.
Let A-small be an array of all elements less than M.

    Que savons-nous sur Une petite et Une grande? Sont-ils la même taille? Peut-être, mais probablement pas.

    Est size(A-small) > k? ou est-il < k?

    Si size(A-small) == k - 1, ça ne ferait pas de M la k-ième plus petit élément?

    Est là quelque chose que nous pouvons faire pour créer une nouvelle valeur de k, et faire un peu de recurrsion ici?

    Je ne suis pas en train de terminer cette pour vous, car il devrait y avoir beaucoup à mâcher. Telles sont les questions que vous devez vous poser. @templatetypedef est de 100% sur la bonne voie, c'est juste de l'expansion sur elle.

    Si vous avez des questions, leur demander, mais il devrait y avoir assez de place ici pour vous permettre de le résoudre sans voler vous de votre exercice mental.

    • Merci pour les conseils, @glowcoder. J'ai été un peu sur la bonne voie grâce à @templatetypedef mais vous faites les choses un peu plus clair pour moi. Aussi, je suis très familier avec ce coup de gueule haha, c'est essentiellement mon père de l'hymne.
    InformationsquelleAutor corsiKa
  2. 8

    Comme astuce, pensez à la façon dont le quicksort partition étape fonctionne. Il divise l'entrée de sorte que le pivot est dans sa position finale, les plus petits éléments sont à gauche, et les plus gros éléments sont à droite. Compte tenu de cette information, et de savoir ce que l'indice que vous tentiez de trouver, pourriez-vous penser à une façon récursive de trouver la kième élément?

    • Je peut très bien être un malentendu, mais cela ne semble pas comme il le serait en O(n). Avec un peu (très peu), la pensée de mon côté, il me semble que si il serait O(n log n).
    • J'ai essayé de mettre en œuvre, mais la seule méthode que j'ai peut arriver, c'est si je trier le tableau d'abord avec quicksort ensuite de retour à la kième élément, mais mon prof explicitement dit de ne pas le faire.
    • Wilkins: je pense que templatetypedef est en faisant allusion à la quickselect algorithme est O(n) prévu (mais O(n2) pour le pire des cas).
    • Wilkins il est O(n) car, à l'opposé de QuickSort, vous pouvez jeter retenir l'autre moitié du tableau après chaque itération. Ainsi, vous disposez de n + n/2 + n/4 + n/8 + ... <= 2*n. +1, bonne réponse.
    • permettez-moi de préciser ce que templatetypedef signifie: Après un split étape de l'algorithme quicksort vous savez combien d'éléments sont plus petit que le pivot, et combien sont grands. Avec cette connaissance et votre K, vous pouvez décider avec qui set pour passer. Ce n'est pas le tri.
    • Qui fait sens. Merci. +1 pour la réponse.
    • L'espoir de (et la plupart du temps prévu) résultat N + N/2 + N/4,..., mais dans le pire des cas de N + N-1 + N-2 + N 3 + N-4..., qui est toujours la N^2.
    • Mais nous sommes encore partiellement tri à moins de trouver le comte.

    InformationsquelleAutor templatetypedef
  3. 0

    De compter les occurrences de chaque entier du tableau dans un autre tableau.

    • Une bonne idée, mais il est de O(L) où L est la plus grande valeur. Cela signifie que si L > 2*n, qui vous ne pouvez pas garantir qu'il ne l'est pas, alors vous perdez votre temps O(n) en moyenne.
    • ou si L = O(n lg lg n), ou certains autres arbitrairement petite étape au-dessus de O(n).
    • Vous avez raison, j'ai mal lu l'exigence
    InformationsquelleAutor Falmarri
  4. 0

    Pour de tels problèmes classiques, wikipédia fonctionne très bien...
    Voir Algorithme de sélection sur wikipédia

    InformationsquelleAutor proactif
  5. 0

    essayez de rechercher l'algorithme de sélection, ou de la sélection de l'algorithme de tri

    InformationsquelleAutor zeacuss
  6. 0
    import java.util.Scanner;


public class JavaApplication1 {
 public static int findpivot(int a,int b,int c){
     //System.out.println("x");
      if(a > b){
        if(c > a){
            return a;
        }
        else if(c > b){
            return c;
        }
        else{
            return b;
        }
    }
    else{
        if(c > b){
            return b;
        }
        else if(c > a){
            return c;
        }
        else{
            return a;
        }
    }
}

public static void find(int arr[],int l,int r,int target){
    //System.out.println(1);
    if(l >= r){
        return;
    }
    int mid = (l+r)/2;
       //System.out.println(1);
    int pivot = findpivot(arr[mid],arr[l],arr[r]);
    int i = l;
    int j = r;
    while(i<=j){
        while(arr[i] < pivot)i++;
        while(arr[j] > pivot)j--;
        if(i<=j){
            int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;//
            i++;
            j--;
        }

    }
    if(target <= (i-1)){
        find(arr,0,i-1,target);
    }
    else{
        find(arr,i,r,target);
    }
}

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int arr[] = new int[n];
            for(int i = 0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            int k = sc.nextInt();
            find(arr,0,n-1,k-1);
            System.out.println(arr[k-1]);
        }

    }

}

    Temps Complexcity est presque O(N).

    InformationsquelleAutor HeadAndTail