查找数组中的特殊数字

Question

数组中有很多数字，除了一个特殊数字出现一次外，每个数字都出现3次。问题是：如何找到数组中的特殊数字？
现在我只能提出一些基数排序和快速排序的方法，无法利用问题的性质。所以我需要一些其他的算法。
感谢您的帮助。

Answer 1

将数字按位 mod 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

既然没人说，我就说：哈希表。

您可以使用简单的哈希表（或哈希图）计算每个元素在数组中出现的次数，时间复杂度为 O(n)。

Answer 3

如果数组已排序，则问题很简单，您只需循环遍历列表，一次三个项目，并检查第三个项目是否与当前项目相同。

如果数组没有排序，可以使用哈希表来统计每个数字出现的次数。

Answer 4

一种可能的算法（非常通用，未经测试）：

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 5

另一种时间复杂度为O(n)、额外空间为O(1)的方法

以下是aj建议的 。我们可以将所有数字相同位置的位相加，并与 3 取模。

总和不是 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;
}

Answer 6

下面的怎么样？

如果我们假设您知道数组中所有数字的最大值和最小值（或者至少可以将它们限制在某个最大范围内，例如 max - min + 1，然后创建一个该大小的辅助数组，并初始化为全零， 现在扫描您的原始数组，例如 MyArray [

]，并为每个元素 MyArray[i] 递增
AuxArray[MyArray[i]] 加一。扫描完成后，将只有一个元素
AuxArray[] 中的值等于 1，并且 AuxArray[] 中该元素的索引将是该特殊数字的值。

这里没有复杂的搜索。只是复杂性的线性顺序。

希望我说得有道理。

约翰·多纳

Answer 7

我没有发现按位 mod 3 的实现非常直观，因此我编写了一个更直观的代码版本，并使用各种示例对其进行了测试，并且它有效。
这是循环内的代码

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 8

我得到了一个解决方案。时间为 O(n)，空间为 O(1)。

n=list(map(int,input().split()))
l=[0]*64
for x in n:
    b=bin(x)[2:]
    b='0'*(64-len(b))+b
    i=0
    while i<len(l):
        l[i]+=int(b[i])
        i+=1
i=0
while i<len(l):
    l[i]%=3
    i+=1
s=''
for x in l:
    s+=str(x)
print(int(s,2))

Answer 9

    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.