Одноместный номер II от leetcode

Question

Вопрос о Единый номер II от leetcode является:

Дан массив целых чисел, каждый элемент появляется три раза, за исключением одного. Найдите этот единственный. Примечание: Ваш алгоритм должен иметь сложность линейного выполнения. Не могли бы вы реализовать его без использования дополнительной памяти?

На самом деле, я уже нашел решение с веб-сайта, решение:

public int singleNumber(int[] A) { 
    int one = 0, two = 0; 
    for (int i = 0; i < A.length; i++) { 
     int one_ = (one^A[i]) & ~two; 
     int two_ = A[i] & one | ~A[i] & two; 
     one = one_; 
     two = two_; 
    } 
    return one; 
} 

Однако, я не знаю, почему этот код может работать и на самом деле я не знаю способ мышления этой проблемы когда я впервые увидел его? Любая помощь. спасибо!

Answer 1

Есть три состояния: 0, 1, 2

Так не может использовать один бит, должны использовать высокий/низкий бит, чтобы представить их как: 00, 01, 10

Вот логика:

высокий/низкий 00 01 10

х = 0 00 01 10

х = 1 01 10 00

high - это функция как высокого, так и низкого уровня.

Если низкий == 1, то высокий = х, еще высокий = высокий & ~ х

Мы

высокий = низкий & х | высокая & ~ х

Это соответствует вашему: "INT two_ = A [I] & один | ~ A [я] & два;"

Аналогично мы имеем низко как функции обоих высокого и низкого:

Если высокий == 1, то низкое = ~ х, то низкий = низкий XOR х

Answer 2

Идея заключается в том, чтобы переинтерпретировать число, как векторов над GF (3). Каждый бит исходного числа становится компонентом вектора. Важная часть состоит в том, что для каждого вектора v в векторном пространстве GF (3) суммирование v + v + v дает 0. Таким образом, сумма по всем векторам оставит единственный вектор и отменит все остальные. Затем результат интерпретируется снова как число, которое является искомым одиночным числом.

Каждый компонент вектора GF (3) может иметь значения 0, 1, 2 с добавлением, выполняемым по модулю 3. «Один» фиксирует низкие биты, а «два» фиксирует высокие биты результата. Поэтому, хотя алгоритм выглядит сложным, все, что он делает, это «цифровое добавление по модулю 3 без переноса».

Answer 3

У меня есть решение более простой:

int singleNumber(int A[], int n) { 
    int one = 0, two = 0, three = ~0; 

    for(int i = 0; i < n; ++i) { 
     int cur = A[i]; 
     int one_next = (one & (~cur)) | (cur & three); 
     int two_next = (two & (~cur)) | (cur & one); 
     int three_next = (three & (~cur)) | (cur & two); 
     one = one_next; 
     two = two_next; 
     three = three_next; 
    } 

    return one; 
} 

Answer 4

первое, что пришло мне в голову, это больше, но более простым для понимания. Просто реализуйте добавочный мод на 3.

*

class Solution { 
    public: 
     int sum3[34], bit[33]; 
     int singleNumber(int A[], int n) { 
      int ans(0); 
      for(int i=0;i<33;i++){ 
       bit[i + 1] = 1<<i; 
      } 
      int aj; 
      for(int i=0;i<n;i++){ 
        for(int j=1;j<33;j++){ 
         aj = abs(A[i]); 
        if(bit[j] & aj) sum3[j]++; 
       } 
      } 
      for(int i=0;i<33;i++){ 
       sum3[i] %= 3; 
       if(sum3[i] == 1) ans += bit[i]; 
      } 
      int positve(0); 
      for(int i=0;i<n;i++){ 
       if(A[i] == ans){ 
        positve++; 
       } 
      } 
      if(positve%3 == 1) 
      return ans; 
      else return -ans; 
     } 
    }; 

*

Answer 5

Вот еще одно решение.

public class Solution { 
     public int singleNumber(int[] nums) { 
      int p = 0; 
      int q = 0; 
      for(int i = 0; i<nums.length; i++){ 
       p = q & (p^nums[i]); 
       q = p | (q^nums[i]); 
      } 
      return q; 
     } 
    } 

Анализ результатов с this blog post.