Étant donné un tableau d'entiers où certains nombres de répétition 1 fois ou 2 fois, mais un nombre répète 3 fois, comment avez-vous trouver?

Je suppose que le tableau n'est pas trié, ou de même, les répétitions d'un certain nombre n'apparaissent pas dans une seule course. Sinon, le problème est vraiment trivial: il suffit de scanner le tableau une fois avec une fenêtre de taille 3, et si chaque nombre dans cette fenêtre est la même, c'est le nombre qui se répète 3 fois en une seule exécution.

Si les répétitions sont dispersés, alors le problème devient plus intéressant.

Puisque c'est les devoirs, je vais seulement vous donner un indice.

Ce problème est un cousin de l'endroit où vous êtes donné un tableau d'entiers non triés, et tous les numéros apparaissent un nombre pair de fois, à l'exception de celui qui apparaît un nombre impair de fois.

Ce numéro peut être trouvé assez facilement dans O(N) par l'exécution d'un ou-exclusif de tous les nombres dans le tableau; le résultat est le nombre qui apparaît un nombre impair de fois.

La raison pour laquelle cela fonctionne est que x xor x = 0.

Ainsi, par exemple, 3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7.

Voici une réponse qui suppose max(A) est raisonnablement petit, où A est le tableau d'entrée:

int ValidCount(int[] a, int[] b, int i, int n) {
  int num = a[i];
  int ret = 0;
  if (b[3*num] >= 0 && b[3*num] < n && a[b[3*num]] == num) ret++;
  if (b[3*num+1] >= 0 && b[3*num+1] < n && a[b[3*num+1]] == num) ret++;
  if (b[3*num+1] >= 0 && b[3*num+2] < n && a[b[3*num+2]] == num) ret++;
  b[3*num+ret] = i;
  return ++ret;
}

int threerep(int[] A, int aSize) {
  int *B = malloc(sizeof(int) * 3 * max(A, aSize)); /* Problematic if max(A) is large */
  /* Note that we don't rely on B being initialized before use */
  for(int i = 0; i < aSize; i++) {
    if (ValidCount(A, B, i, aSize) == 3) return A[i];
  }
  return ERROR_NO_ANSWER;
}

Bien tout ce que je peux penser à est de cela, mais je suis sûr que votre prof est à la recherche d'une délicate équation qui permettra de résoudre ce dans 1 scan. Vous pouvez le faire dans les 2 scans qui est O(n) en supposant que vous pouvez créer un 2ème tableau de taille (de 0 à max nombre dans le 1er tableau). Scan une fois, trouver le nombre maximal de numéros dans le tableau. Créer 2e tableau de cette taille. Itération sur le 1er tableau, en utilisant à nouveau le 2ème tableau, comme des seaux pour incrémenter le nombre de chaque élément dans le 1er tableau. Une fois que vous incrémenter un seau à 3, c'est votre solution. Pas le meilleur, mais il pourrait fonctionner dans certains cas.

Bugaoo l'algorithme de l'air soigné, qui est cité ci-dessous. En fait, on peut généraliser en faisant un supplément de passer avant "1er pass" pour trouver min () et max(A) et d'un supplément de passer pour déplacer chaque élément de la gamme de la fonction min () et max(A), c'est à dire, Un[0]-min(A). Après un 1er passage" et "2ème pass" (notez que nous devrions mod les éléments par max(A)-min(A) au lieu de n), on pourrait ajouter min(A), le double du nombre trouvé à la dernière.

Essentiellement, le problème est de calculer la mode de la matrice. Cette solution fonctionne "SEULEMENT" si le tableau de la gamme [0,n-1]. Mettre la solution ici, puisque le problème n'est pas de mettre une clause de la gamme.
Supposons que n est la taille de la arrayScan le tableau et marquer Un[A[i]]=A[A[i]]+n -----> 1er passage
Diviser chaque élément du tableau par des 'n', j'.e A[i]=A[i]/n ----> 2e col
L'élément avec la valeur maximale de la 2ème passe est la réponse.
Ce est O(n) O(1) espace (mais avec une clause range).
Je ne suis pas au courant de tout algorithme pour calculer la mode en temps O(n),O(1) avec pas de clauses sur la plage.

int count[2^32]; 
pour x en entrée: 
le comte[x] = 0; //supprimer cette boucle si vous pouvez assumer la ram est autorisé à 0. 
pour x en entrée: 
le comte[x]++; 
pour x en entrée: 
si count[x] == 3: 
retour x 

S'il vous plaît excusez le mélange de langues 🙂 Aussi, c'est vraiment stupide d'avoir un tableau qui peut être indexé par un entier quelconque, vous pouvez le faire sur un système 64 bits, et il est conforme aux exigences.

Je vais vous présenter une solution qui fonctionne, en général, tels qu'un numéro de produit m times et d'autres n fois.

Nous avons besoin d'un opérateur qui annule n occurrences d'un nombre entier, mais conserve m occurrences. Si l'on convertit chaque numéro de sa représentation binaire, et pour chaque position de bit, compter le nombre de fois que ce bit est défini, la valeur sera un multiple de n pour tous les nombres qui se produisent n fois, plus 0 ou m pour le bit correspondant de la lone entier.

Si nous prenons ensuite modulo n de chacune de ces chiffres, et diviser par m, le résultat est la valeur du bit correspondant pour le seul entier. Tout ce qui reste est de convertir le résultat en binaire à décimal formelle.

For example, given array = [3, -4, 3, 3], m = 1 and n = 3:
Binary of 3 = 011
Binary of -4 (2s complement) = 11111111111111111111111111111100

Bit 0: 3 % 3 = 0
Bit 1: 3 % 3 = 0
Bit 2 through 32: 1 % 3 = 1
The result is -4