Algorithme pour trouver la plus petite différence d'index de nombres égaux dans un tableau

Question

Quelqu'un a-t-il une idée de la façon de résoudre le problème suivant ?

Nous avons un tableau, par exemple, laissez-le être a = {1, 0, -1, -2, -1, 0, 1, 2, 3, 4, 5, 1}.

Ce que l'algorithme devrait trouver est la taille de la plus petite différence entre les indices des mêmes nombres. Dans cet exemple (tableau a) la différence des indices des uns est 6-0=0 et 11-6=5, la différence des indices des zéros est 5-1=4, la différence des indices des moins un est 4-2=2 et ainsi de suite. Et l'algorithme devrait retourner 2 car nous pouvons voir que c'est la plus petite différence d'indices des mêmes nombres.

Existe-t-il un moyen de résoudre ce problème avec une complexité temporelle meilleure que O(n^2) ?

Answer 1

Plusieurs autres réponses proposent de trier des paires (élément, indice), ce qui peut être fait en O(n*logn). Cependant, il est possible de faire mieux, en seulement O(n) temps. Il n'est pas nécessaire de trier le tableau, ni de conserver toutes les paires (élément, indice), puisque le minimum peut être trouvé avec avidité.

Bouclez à travers le tableau une fois et stockez le dernier index de chaque élément dans un hash.

int smallestDifference(int[] a) {
    Map<Integer, Integer> lastIndex = new HashMap<>();
    int minDiff = Integer.MAX_VALUE;
    for (int i = 0; i < a.length; i++) {
        if (lastIndex.contains(a[i])) {
            minDiff = Math.min(minDiff, i - lastIndex.get(a[i]));
        }
        lastIndex.put(a[i], i);
    }
    return minDiff;
}

Insérer/obtenir à partir du hachage est O(1), ce qui vous donne O(n) pour l'ensemble du tableau.

Answer 2

Faire vector<pair<int, int>> qui stocke les valeurs du vecteur original avec leurs indices respectifs. Pour chaque valeur v dont l'indice est i, on ajoute (v,i) au vecteur.

Trier le vecteur (par valeur puis par indice).

Ensuite, parcourez le vecteur trié et trouvez la plus petite (ou la plus grande, si vous voulez) distance entre les éléments de même valeur.

Cela prend O(n log n) étapes.

Answer 3

Tout d'abord, vous pouvez ajouter des index à votre séquence (O(N)) :

> L = [1, 0, -1, -2, -1, 0, 1, 2, 3, 4, 5, 1].
[1,0,-1,-2,-1,0,1,2,3,4,5,1]
> LI = lists:zip(L, lists:seq(1, length(L))).
[{1,1},
 {0,2},
 {-1,3},
 {-2,4},
 {-1,5},
 {0,6},
 {1,7},
 {2,8},
 {3,9},
 {4,10},
 {5,11},
 {1,12}]

Ensuite, vous le triez (O(N log N)) :

> LS = lists:sort(LI).
[{-2,4},
 {-1,3},
 {-1,5},
 {0,2},
 {0,6},
 {1,1},
 {1,7},
 {1,12},
 {2,8},
 {3,9},
 {4,10},
 {5,11}]

Ensuite, vous trouvez les distances de toutes les mêmes valeurs (O(N)) :

> LD = (fun F([{X, P1}|[{X,P2}|_]=T]) -> [{P2-P1, X, {P1, P2}} | F(T)]; F([_|T]) -> F(T); F([]) -> [] end)(LS).
[{2,-1,{3,5}},{4,0,{2,6}},{6,1,{1,7}},{5,1,{7,12}}]

Ensuite, vous trouvez la distance minimale (O(N)) :

> lists:min(LD).
{2,-1,{3,5}}

Cela signifie une distance minimale 2 de valeur -1 entre les positions 3 et 5 et la complexité du résultat est O(N log N). (L'exemple de code est en Erlang).

Answer 4

L'algo suivant fonctionnera dans O(nlogn)

 1) Make a map of <int,vector<int> > .
    2) Let the number be the key and the indexes be the vector.
    3) sort the vector for all the keys.
    4) Now find the minimum difference for all the difference between indices.

Par exemple : Pour le tableau 1 2 3 2 1 3

1 -> [0,4]
2 ->[1,3]
3 -> [2,5]

Ici, nous pouvons voir que 3-1 = 2 donnera la différence minimale dans les indices.

Answer 5

Il est écrit dans le langage de programmation Go.

func smallestIndexDifference(numbers []int) (mindiff int, exists bool) {
  var prev map[int]int // The previous index where this number was found
  for i, number := range numbers {
    prevIndex, found := prev[number]
    if found {
      diff := i - prevDiff
      if !exists || diff < mindiff {
        exists, mindiff = true, diff
      }
    }
    prev[number] = i
  }
  return
}

Ceci n'a pas été testé, mais si cela fonctionne, ce sera en O(n log n).