Trouvez l'élément ayant le plus de "voisins" dans une séquence

Question

Supposons que nous ayons une séquence S avec n éléments <x1,x2,...,xn>. Une paire d'éléments xi,xj sont considérés comme voisins si |xi-xj|<d, avec d une distance donnée entre deux voisins. Alors, comment trouver l'élément qui a le plus de voisins dans la séquence?

(Une façon simple trie la séquence, puis en calculant le nombre de chaque élément, mais il est la complexité de temps est assez grand):

O(nlogn) 

Puissiez-vous s'il vous plaît me aider à trouver une meilleure façon de réduire la complexité du temps?

Answer 1

O(N log N) n'est pas "assez grand"; log est une fonction de croissance très lente!

Cela ne peut pas être fait dans un temps inférieur à O(N) puisque vous devez lire toute l'entrée. Vous pouvez le faire en O(N) si vous connaissez la plage des nombres, auquel cas vous pouvez utiliser l'une des méthodes de tri O(N) (par exemple, tri par tri/tri de seau, tri de base).

---

est ici une solution O(dN) de -temps, O(N + k) -espace basé sur tri par comptage, mis en œuvre en Java.

static int mostNeighbors(int k, int d, int... nums) { 
    boolean[] appears = new boolean[k]; 
    int[] neighborCount = new int[k]; 
    int most = 0; 
    for (int num : nums) { 
     appears[num] = true; 
     for (int i = num - d + 1; i < num + d; i++) { 
      if (i < 0 || i >= k) continue; 
      if (++neighborCount[i] > neighborCount[most] && appears[i]) { 
       most = i; 
      } 
     } 
    } 
    return most; 
} 

// ... 
System.out.println(mostNeighbors(10, 2, 0,0,0,2,2,2)); // prints 0 
System.out.println(mostNeighbors(10, 2, 0,0,0,2,2,2,1)); // prints 1 
System.out.println(mostNeighbors(10, 2, 1,2,3,4,5,3)); // prints 2 

Fondamentalement, pour chaque num, il incrémente neighborCount[num-d+1..num+d-1] qui sont dans la gamme de 0..k-1. Tous les nombres de cette plage n'apparaissent pas dans le tableau, donc appears est utilisé pour garder une trace de cela. most est utilisé pour garder une trace des meilleurs trouvés jusqu'à présent.