Single Number II из leetcode

Вопрос о Single Number 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;
}

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

Ответы

Ответ 1

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

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

Ответ 2

Существует три состояния: 0, 1, 2

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

Здесь логика:

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

x = 0 00 01 10

x = 1 01 10 00

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

Если low == 1, то high = x, иначе high = high и ~ x

Мы имеем

высокий = низкий и x | высокий и ~ x

Это равно вашему: "int two_ = A [i] и одному | ~ A [i] и двум;"

Аналогично, мы имеем низкую функцию как высокой, так и низкой:

Если high == 1, то low = ~ x, иначе low = low XOR x

Ответ 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;
}

Ответ 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;
        }
    };

*

Ответ 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;  
        }  
    }

Анализ этого сообщения в блоге.