Recherche d'un nombre spécial dans un tableau

Question

Il existe plusieurs nombres dans un tableau et chaque nombre apparaît trois fois, à l'exception d'un numéro spécial qui apparaît une seule fois. Voici la question: comment puis-je trouver le numéro spécial dans le tableau?
Maintenant je ne peux que mettre en avant quelques méthodes avec le tri de base et le tri rapide qui ne peuvent pas tirer profit de la propriété de la question. J'ai donc besoin d'autres algorithmes.
Merci pour votre aide.

Answer 1

Additionnez les chiffres mod 3 bit, par exemple

def special(lst): 
    ones = 0 
    twos = 0 
    for x in lst: 
     twos |= ones & x 
     ones ^= x 
     not_threes = ~(ones & twos) 
     ones &= not_threes 
     twos &= not_threes 
    return ones 

Answer 2

Puisque personne ne le dit, je vais: hashtable.

Vous pouvez calculer le nombre de fois où chaque élément se trouve dans le tableau en O(n) avec une simple hashtable (ou hashmap).

Answer 3

Si le tableau est trié, le problème est trivial, il vous suffit de parcourir la liste, trois éléments à la fois, et de vérifier si le troisième élément est le même que le courant.

Si le tableau n'est pas trié, vous pouvez utiliser une table de hachage pour compter le nombre d'occurrences de chaque nombre.

Answer 4

Que diriez-vous de ce qui suit? Si nous supposons que vous connaissez les valeurs maximum et minimum de tous les nombres du tableau (ou pouvez au moins les limiter à une certaine gamme maximum, disons max - min + 1, alors créez un tableau auxiliaire de cette taille, initialisé Pour tous les zéros, dites AuxArray [].

Maintenant, scannez votre tableau d'origine, dites MyArray [], et pour chaque élément MyArray [i], incrémentez de AuxArray [MyArray [i]] par un. , il y aura exactement un élément dans AuxArray [] égal à un, et l'indice de cet élément dans AuxArray [] sera la valeur du nombre spécial

Pas de recherche compliquée ici. t un ordre linéaire de complexité.

J'espère que j'ai fait sens.

John Doner

Answer 5

Un algorithme possible (très générique, non testé):

function findMagicNumber(arr[0...n]) 
    magic_n := NaN 

    if n = 1 then 
     magic_n := arr[0] 
    else if n > 1 then 
     quicksort(arr) 

     old_n := arr[0] 
     repeat := 0 

     for i := 1 to n 
     cur_n := arr[i] 
     repeat := repeat + 1 
     if cur_n ≠ old_n then 
      if repeat = 1 then 
       magic_n := old_n 
      old_n := cur_n 
      repeat := 0 

    return magic_n 

Answer 6

Je ne ai pas trouvé la mise en œuvre du mod 3 très intuitive bitwise j'ai écrit donc une version plus intiuitive du code et testé avec divers exemples et cela a fonctionné. Voici le code à l'intérieur de la boucle

threes=twos&x //=find all bits counting exactly thrice 
x&=~threes //remove the bits countring thrice from x as well as twos 
twos&=~threes 

twos|=ones&x //find all bits counting exactly twice 
x&=~twos //remove all bits counting twice from modified x as well as ones 
ones&=~twos 

ones|=x //find all the bits from previous ones and modified x 

vous espérez trouver les gars, il est facile de comprendre cette version du code.

Answer 7

int main() 
    { 
      int B[] = {1,1,1,3,3,3,20,4,4,4}; 
      int ones = 0 ; 
      int twos = 0 ; 
      int not_threes; 
      int x ; 

     for(i=0; i< 10; i++) 
     { 
     x = B[i]; 
      twos |= ones & x ; 
      ones ^= x ; 
      not_threes = ~(ones & twos) ; 
      ones &= not_threes ; 
      twos &= not_threes ; 
     } 

     printf("\n unique element = %d \n", ones); 

     return 0; 

    } 


The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer. 

Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element. 
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer. 

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want. 

To rectify this mistake, the code makes use of 2 variables. 
ones - At any point of time, this variable holds XOR of all the elements which have 
appeared "only" once. 
twos - At any point of time, this variable holds XOR of all the elements which have 
appeared "only" twice. 

So if at any point time, 
1. A new number appears - It gets XOR'd to the variable "ones". 
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the 
variable "twice". 
3. A number appears for the third time - It gets removed from both "ones" and "twice". 

The final answer we want is the value present in "ones" - coz, it holds the unique element. 

So if we explain how steps 1 to 3 happens in the code, we are done. 
Before explaining above 3 steps, lets look at last three lines of the code, 

not_threes = ~(ones & twos) 
ones & = not_threes 
twos & = not_threes 

All it does is, common 1's between "ones" and "twos" are converted to zero. 

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order). 

Explanation for step 1 
------------------------ 
Lets say a new element(x) appears. 
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x". 

Observe the statement "twos| = ones & x". 
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x". 
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos". 

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros. 
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing. 

Explanation for step 2. 
------------------------ 
Lets say an element(x) appears twice. 
CURRENT SITUATION - "ones" has recorded "x" but not "twos". 

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x. 
But due to the statement, "ones^= x" - "ones" removes "x" from its binary representation. 

Again, last 3 lines of code does nothing. 
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x". 

Explanation for step 3. 
------------------------- 
Lets say an element(x) appears for the third time. 
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has. 

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x". 
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x". 

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x". 
Thus both "ones" and "twos" ends up losing bit representation of "x". 

1st example 
------------ 
2, 2, 2, 4 

After first iteration, 
ones = 2, twos = 0 
After second iteration, 
ones = 0, twos = 2 
After third iteration, 
ones = 0, twos = 0 
After fourth iteration, 
ones = 4, twos = 0 

2nd example 
------------ 
4, 2, 2, 2 

After first iteration, 
ones = 4, twos = 0 
After second iteration, 
ones = 6, twos = 0 
After third iteration, 
ones = 4, twos = 2 
After fourth iteration, 
ones = 4, twos = 0 

Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer. 

Answer 8

suivant est un autre O (n) complexité temporelle et O (1) Méthode d'espace supplémentaire

suggéré par aj. On peut additionner les bits dans les mêmes positions pour tous les nombres et prendre modulo avec 3.

Les bits pour lesquels la somme n'est pas multiple de 3, sont les bits de nombre à occurrence unique. Considérons

l'exemple de tableau {5, 5, 5, 8}.

Le 101, 101, 101, 1000

Somme des premiers bits% 3 = (1 + 1 + 1 + 0)% 3 = 0;

Somme des deuxièmes bits% 3 = (0 + 0 + 0 + 0)% 0 = 0;

Somme des troisièmes bits% 3 = (1 + 1 + 1 + 0)% 3 = 0;

Somme des quatrièmes bits% 3 = (1)% 3 = 1;

nombre conséquent qui apparaît une fois est 1000

#include <stdio.h> 
#define INT_SIZE 32 

int getSingle(int arr[], int n) 
{ 
// Initialize result 
int result = 0; 

int x, sum; 

// Iterate through every bit 
for (int i = 0; i < INT_SIZE; i++) 
{ 
    // Find sum of set bits at ith position in all 
    // array elements 
    sum = 0; 
    x = (1 << i); 
    for (int j=0; j< n; j++) 
    { 
     if (arr[j] & x) 
     sum++; 
    } 

    // The bits with sum not multiple of 3, are the 
    // bits of element with single occurrence. 
    if (sum % 3) 
    result |= x; 
} 

return result; 
} 

// Driver program to test above function 
int main() 
{ 
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7}; 
int n = sizeof(arr)/sizeof(arr[0]); 
printf("The element with single occurrence is %d ",getSingle(arr, n)); 
return 0; 
}