查找數組中的特殊數字

Question

數組中有許多數字，每個數字出現三次，除了一次出現一個特殊數字。這裏是一個問題：我怎樣才能找到數組中的特殊數字？
現在我只能提出一些基數排序和快速排序的方法，不能利用問題的屬性。所以我需要一些其他算法。
感謝您的幫助。

Answer 1

添加數字逐位模3，例如

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

既然沒人說，我會：hashtable。

您可以使用簡單哈希表（或散列表）計算O(n)中每個元素出現在數組中的次數。

Answer 3

如果對數組進行排序，問題很簡單，您只需遍歷列表中的三個項目，並檢查第三個項目是否與當前項目相同。

如果數組未被排序，您可以使用散列表來計算每個數字的出現次數。

Answer 4

以下情況如何？如果我們假設你知道數組中所有數字的最大值和最小值（或者至少可以將它們限制在某個最大範圍內，比如max - min + 1，那麼創建一個這樣大小的輔助數組，初始化例如AuxArray []。

現在掃描您的原始數組，例如MyArray []，併爲每個元素MyArray [i]，遞增 AuxArray [MyArray [i]]加1。 ，在AuxArray []中只會有一個元素 等於1，並且AuxArray []中該元素的索引將是特殊數字的值

這裏沒有複雜的搜索。 t是複雜性的線性順序。

希望我有道理。

約翰多納

Answer 5

一種可能的算法（很通用的，未測試）：

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

我沒有找到按位模3非常直觀的實現，因此我寫的代碼更intiuitive版本，並通過不同的例子測試它和它的工作。 這裏是循環內的代碼

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 

希望你們會發現很容易理解這個版本的代碼。

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

以下是另一個O（n）的時間由AJ建議的複雜性和O（1）額外的空間方法

。我們可以在所有數字的相同位置上對位進行求和並以3爲模。

其中sum不是3的倍數的位是單次出現的位數。 讓我們考慮

示例數組{5，5，5，8}。

的101,101，101，1000

第一比特薩姆％3 =（1 + 1 + 1 + 0）％3 = 0;

第二位的總和％3 =（0 + 0 + 0 + 0）％0 = 0;

第三位之和％3 =（1 + 1 + 1 + 0）％3 = 0;

第四位的和％3 =（1）％3 = 1;

出現一次因此數爲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; 
}