trouver kth plus grand élément dans un sac mis en œuvre par matrice

Question

Nous avons une collection de Comparable s tenue dans un sac et doit trouver le k ème élément le plus grand. J'ai copié la collection sur un HashSet pour supprimer les doublons, puis j'ai converti le HashSet en un tableau à trier et par conséquent l'k ème élément accédé. Le code compile, mais échoue le test, et je ne peux pas comprendre ce qui ne va pas. Des idées?

public E kth(int k) { 
    uniqueSet(); 
    Object[] uniqueArr = hashSet.toArray(); 
    startQuick(uniqueArr); 
    return (E) uniqueArr[k - 1]; 
} 

private void startQuick(Object[] uniqueArr) { 
    int i = 0, j = uniqueArr.length; 
    quickSort(uniqueArr, 0, j); 
} 

private void quickSort(Object[] uniqueArr, int i, int j) { 
    int index = partition(uniqueArr, i, j); 
    if (i < index - 1) { 
     quickSort(rankBagArr, index - 1, j); 
    } 
    if (index < j) { 
     quickSort(rankBagArr, i, index - 1); 
    } 
} 

private int partition(Object[] uniqueArr, int i, int j) { 
    E tmp; 
    E pivot = (E) rankBagArr[(i + j)/2]; 

    while (i <= j) { 
     while (rankBagArr[i].compareTo(pivot) < 0) { 
      i++; 
     } 
     while (rankBagArr[j].compareTo(pivot) > 0) { 
      j--; 
     } 

     if (i <= j) { 
      tmp = (E) rankBagArr[i]; 
      rankBagArr[i] = rankBagArr[j]; 
      rankBagArr[j] = tmp; 
      i++; 
      j--; 
     } 
    } 
    return i; 
} 

Answer 1

Pour commencer cette partie est très suspect:

if (i < index - 1) 
     quickSort(rankBagArr, index-1 ,j); 
    if (index < j) 
     quickSort(rankBagArr, i, index-1); 

Ne pas vous dire:

if (i < index - 1) 
     quickSort(rankBagArr, i, index-1); 
    if (index + 1 < j) 
     quickSort(rankBagArr, index + 1, j); 

?

Je ne connais pas votre approche du partitionnement, donc je ne sais pas si c'est correct ou non. I pense Je le comprends, et cela semble correct lors de l'inspection, mais il est très facile d'obtenir des erreurs hors-un qui sont difficiles à voir sans une étude minutieuse.

Voici une méthode de partition que j'ai écrite en C# récemment - vous devriez pouvoir la traduire assez facilement en Java si vous le souhaitez.

private static int Partition<T>(T[] array, int left, int right, 
    IComparer<T> comparer) { 
    // Pivot on the rightmost element to avoid an extra swap 
    T pivotValue = array[right]; 
    int storeIndex = left; 
    for (int i = left; i < right; i++) { 
    if (comparer.Compare(array[i], pivotValue) < 0) { 
     Swap(array, i, storeIndex); 
     storeIndex++; 
    } 
    } 
    Swap(array, right, storeIndex); 
    return storeIndex; 
} 

static void Swap<T>(T[] array, int x, int y) { 
    T tmp = array[x]; 
    array[x] = array[y]; 
    array[y] = tmp; 
} 

Une raison de ne pas simplement utiliser Arrays.sort?

Answer 2

mai vous pourriez avoir un peu moins de manipulations (et améliorer la performance), et corriger le défaut que vous voyez ...

A partir d'une liste (ArrayList), vous pouvez demander de faire le tri (en utilisant le comparateur, et Collections.sort(list)). Ensuite, on boucle pourrait descendre et:

• mémoriser le dernier élément
• si vous trouvez le nouvel élément n'est pas égal à égal, incrémenter un compteur
• lorsque votre compteur atteint la valeur de k, l'élément courant est votre cible

Answer 3

Si vous voulez résoudre le problème par le tri, puis

1. Utiliser des méthodes de tri de l'API (Arrays.sort ou Collections.sort). Réinventer la roue est inutile.
2. Trier le contenu de votre collection une fois, pas à chaque fois que vous recherchez un élément k.

Le partitionnement de quicksort est bon pour trouver l'élément k-ième sans tri collection - si elle est plus petit alors k, vous partition, si la plus basse gamme est plus grand alors k, vous allez de façon récurrente avec la partition à la gamme inférieure, vous allez à plus haut de gamme et chercher (k - taille de la gamme inférieure) -ième élément. Il a une meilleure complexité que le tri de la collection entière. Vous pouvez en lire plus à ce sujet here

De toute façon, vos méthodes ont un paramètre nommé uniqueArr, mais certaines opérations que vous effectuez sur rankBagArr. Est-ce une faute de frappe? Il n'y a pas de définition de rankBagArr dans votre code.