Méthode efficace pour trouver une paire avec la différence minimale dans un tableau

Question

J'essaie de résoudre un problème qui me demande de trouver une paire avec une différence minimale dans un tableau.

Par exemple, si la matrice est

6,7,1,3,9 

La sortie est

(6,7) 

avec une différence de 1, qui est minimum.

La solution la plus rapide que je puisse trouver consiste à trier le tableau et à parcourir le tableau trié pour trouver la différence minimale [O (nlogn)]. Existe-t-il un moyen d'optimiser cela ou de mieux le résoudre en O (n) ou O (logn)? Editer: Tous les éléments du tableau sont distincts.

Answer 1

En supposant que tous les nombres sont distincts et sécrètent, vous pouvez arrêter votre recherche une fois que la différence est 1.

Il y a aussi un article de wikipedia ici sur ce problème: https://en.wikipedia.org/wiki/Closest_pair_of_points_problem

également une autre question ici: Finding out the minimum difference between elements in an arrays

Mon amélioration:

int[] a = new int[] {4, 9, 1, 32, 13}; 
Arrays.sort(a); 
int minDiff = a[1]-a[0]; 
for (int i = 2 ; i != a.length ; i++) { 
    minDiff = Math.min(minDiff, a[i]-a[i-1]); 
    if (minDif == 1) 
     break; 
} 
System.out.println(minDiff); 

Answer 2

Je ne vous attendez pouvez trouver un O(log n) solution car il y a au moins un besoin d'itérer sur tout un tableau pour voir ses éléments. Pour moi l'approche de tri semble optimale mais il y a une possibilité d'améliorer la complexité O(n log n) si vos nombres proviennent d'un ensemble pas si grand qui est connu avant (par exemple des nombres entiers de la plage [0; N] pour un assez petit N). Dans ce cas, vous pouvez utiliser l'algorithme de tri par comptage pour lequel la complexité dans le pire des cas est O(n + N). Cependant, s'il vous plaît noter que l'utilisation de l'espace est également O(n + N). Il y a beaucoup de sources sur le genre de comptage et celui-ci devrait être suffisant: https://en.wikipedia.org/wiki/Counting_sort

Answer 3

Vous essayez de résoudre le problème Closest Pair, dans lequel vous recherchez les deux points de votre jeu de données qui ont la distance minimale entre eux. Définir la dimension à 1 réduit à votre cas (un point est juste un nombre).

La complexité temporelle des algorithmes pour résoudre ce problème est efficace:

O (nlogn)

Notez que diviser et techniques Conquer peuvent être utilisées dans ce contexte. Comme par exemple dans ces slides. Astuce: Si vous supposez que les points de données sont distincts, alors vous pouvez arrêter votre algorithme lorsque vous trouvez une distance de 1 (puisqu'il ne peut pas être inférieur à 1), mais cela pourrait ne jamais être le cas pour vos données.