Найти специальное число в массиве

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) с помощью простой таблицы хеш-таблиц (или hashmap).

Answer 3

Ниже приводится еще одна 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 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

Если массив отсортирован, проблема тривиальна, вы просто просматриваете список по три элемента за раз и проверяете, совпадает ли третий элемент с текущим.

Если массив не отсортирован, вы можете использовать хэш-таблицу для подсчета количества вхождений каждого числа.

Answer 6

У меня есть решение.Это 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 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

Я не считаю реализацию побитового мода 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 9

Как насчет следующего?

Если предположить, что вам известны максимальные и минимальные значения всех чисел в массиве (или вы можете хотя бы ограничить их до некоторого максимального диапазона, скажем, max - min + 1,затем создайте вспомогательный массив этого размера, инициализированный для всех нулей, скажем, AuxArray [].

Теперь просканируйте исходный массив, скажем, MyArray [], и для каждого элемента MyArray [i] увеличьте значение AuxArray [MyArray [i]] на единицу. После завершения сканирования в AuxArray [] будет ровно один элемент, равный единице, и индекс этого элемента в AuxArray [] будет значением специального числа.

Здесь нет сложного поиска. Просто линейный порядок сложности.

Надеюсь, я понял.

Джон Донер