Одиночный номер II из leetcode

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

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

Итак, я столкнулся с некоторыми проблемами с кодированием и довольно долго придерживался этого, и после тонны исследований в Google, просматривая разные сообщения и порталы, я понял эту проблему. Постараюсь объяснить как можно проще.

Задача имеет 3 решения:

1. Использование HashMap. Но, как мы знаем, это добавит O(N) пространственной сложности, а мы этого не хотим. Но для небольшого понимания подход заключается в повторении массива, подсчете цифр и сохранении его на карте. Затем повторите карту, и там, где количество равно 1, это будет ваш ответ.
2. Использование побитовых операторов. Логика этого подхода заключается в том, чтобы представить числа в битах, а затем добавить все биты каждой позиции. Итак, после сложения вы увидите, что сумма либо кратна 3, либо кратна 3 + 1 (поскольку другое число встречается только один раз). После этого, если вы сделаете по модулю эту сумму, вы получите результат. Вы лучше поймете на примере.
   
   Пример: Массив - [5, 5, 5, 6]
   5 представлено в битах: 101
   6 представлено в битах: 110
   
   [ 101, 101, 101, 110] (Двоичное представление значений)
   После добавления к определенным позициям у нас будет
   0-й -> 3,1-й -> 1, 2-й -> 4
   и если вы mod на 3 станет
   0-й -> 0, 1-й -> 1,2-й -> 1
   что в десятичном представлении и будет нашим ответом 6.
   Теперь нам нужно закодировать то же самое. Я объяснил код с помощью комментариев.
   

public class SingleNumberII {
    /*
    * Because the max integer value will go upto 32 bits
    * */
    private static final int INT_SIZE = 32;

    public int singleNumber(final int[] A) {

        int result = 0;
        for(int bitIterator = 0; bitIterator < INT_SIZE; bitIterator++) {
            int sum = 0, mask = (1 << bitIterator);
            /*
            * Mask: 
            * 1 << any number means -> it will add that number of 0 in right of 1
            * 1 << 2 -> 100
            * Why we need mask? So when we do addition we will only count 1's,
            * this mask will help us do that
            * */
            for(int arrIterator = 0; arrIterator < A.length; arrIterator++) {
                /*
                * The next line is to do the sum.
                * So 1 & 1 -> 0
                * 1 & 0 -> 0
                * The if statement will add only when there is 1 present at the position
                * */
                if((A[arrIterator] & mask) != 0) {
                    sum++;
                }
            }

            /*
            * So if there were 3 1's and 1 0's
            * the result will become 0
            * */
            if(sum % 3 == 1) {
                result |= mask;
            }
        }

        /*So if we dry run our code with the above example
        * bitIterator = 0; result = 0; mask = 1;
        * after for loop the sum at position 0 will became 3. The if 
        * condition will be true for 5 as - (101 & 001 -> 001) and false for 6
        * (110 & 001 -> 000)
        * result -> 0 | 1 -> 0
        * 
        * bitIterator = 1; result = 0; mask = 10;
        * after for loop the sum at position 1 will became 1. The if
        * condition will be true for 6 as - (110 & 010 -> 010) and false for 5
        * (101 & 010 -> 000)
        * result -> 00 | 10 -> 10
        * 
        * bitIterator = 2; result = 10; mask = 100;
        * after for loop the sum at position 2 will became 4. The if
        * condition will be true for 6 as - (110 & 100 -> 100) and true for 5
        * (101 & 100 -> 100)
        * result -> 10 | 100 -> 110 (answer)
        * */
        return result;
    }
}

Как мы видим, это не лучшее решение, потому что нам не нужно повторять его более 32 раз, а также оно не такое уж обобщенное. Что заставляет посетить наш следующий подход.

3. Использование побитовых операторов (оптимизированных и обобщенных):
   Итак, для этого подхода я попытаюсь объяснить подход, затем код, а затем то, как сделать его обобщенным. Возьмем 2 флага (один, два) по аналогии будем считать их наборами. Итак, у нас число появляется 1-й раз, оно будет добавлено в один, только если его нет в два. и мы сделаем то же самое для двух, то есть, если число появится во второй раз, мы удалим его из 1, а затем добавим его к двум (только если его нет в одном) и для числа, появившегося в третий раз, оно будет удалено из набора два и больше не будет существовать ни в одном наборе. У вас может возникнуть вопрос, почему причина 2 наборов (или переменных) объясняется в 4-м пункте.

public int singleNumberOptimized(int[] A) {
    int one = 0, two = 0;
    /*
    * Two sets to maintain the count the number has appeared
    * one -> 1 time
    * two -> 2 time
    * three -> not in any set
    * */
    for(int arrIterator = 0; arrIterator < A.length; arrIterator++){
        /*
        * IF one has a number already remove it, and it does not have that number
        * appeared previously and it is not there in 2 then add it in one.
        * */
        one = (one ^ A[arrIterator]) & ~two;
        /*
         * IF two has a number already remove it, and it does not have that number
         * appeared previously and it is not there in 1 then add it in two.
         * */
        two = (two ^ A[arrIterator]) & ~one;
    }

    /*
    * Dry run
    * First Appearance : one will have two will not
    * Second Appearance : one will remove and two will add
    * Third Appearance: one will not able to add as it is there in two
    * and two will remove because it was there.
    *
    * So one will have only which has occurred once and two will not have anything
    * */
    return one;
}

4. Как решать вопросы такого типа в более общем плане?
   Количество наборов, которые необходимо создать, зависит от значения k (внешнего вида каждого другого целого числа). м >= лог(К). (Чтобы подсчитать количество единиц в массиве таким образом, чтобы всякий раз, когда подсчитанное количество единиц достигает определенного значения, скажем, k, счетчик возвращался к нулю и начинался заново. Чтобы отслеживать, сколько единиц мы встретили до сих пор, нам нужно счетчик. Предположим, что счетчик имеет m бит.) m будет количеством наборов, которые нам нужны.
   Для всего остального мы используем ту же логику. Но подождите, что я должен вернуть, логика состоит в том, чтобы выполнять операции ИЛИ со всеми наборами, которые в конечном итоге будут выполнять операцию ИЛИ над одним числом с самим собой и некоторыми 0, которые интернируются к одному числу. Для лучшего понимания этой конкретной части прочитайте этот пост здесь.
   Я изо всех сил старался объяснить вам решение. Надеюсь, вам понравится.
   #HappyCoding

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

   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;  
        }  
    }  

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

Лучше сделать карту Карно, также известную как K-map. Для карты Карно Ref.

счетчик с 3 состояниями

Соответствующие значения A[i], two, one и two_, one_ после

0 0 0 | 0 0
0 0 1 | 0 1
0 1 0 | 1 0
0 1 1 | X X
1 0 0 | 0 1
1 0 1 | 1 0
1 1 0 | 0 0
1 1 1 | X X

Здесь X означает, что нас не волнует этот случай или просто конечное значение двух и одного, где бы их вывод ни был 1, это также можно учитывать, результат будет одинаковым и для 4-го, и для 8-го случай не будет для него существовать, так как два и один не может быть одним одновременно.

Если вы думаете, как я придумал приведенную выше таблицу. Я собираюсь объяснить один из них. Рассматривая 7-й случай, когда A[i] равно 1, два равно 1, т.е. уже существует A[i], которое повторяется два раза. Наконец, есть 3 A[i]. Так как их 3, то two_ и one_ оба должны сбрасываться на 0.

С учетом one_
значение равно 1 для двух случаев, т. е. 2-го и 5-го. Принятие 1 аналогично рассмотрению minterms в K-map.

one_ = (~A[i] & ~two & one) | (A[i] & ~two & ~one)

Если ~two взять обычное, то

(~A[i] & one) | (A[i] & ~one) will be same as (A[i]^one)

Затем,

one_ = (one ^ A[i]) & ~two

С учетом two_
значение равно 1 для двух случаев, т. е. 3-го и 6-го. Принятие 1 аналогично рассмотрению minterms в K-map.

two_ = (~A[i] & two & ~one) | (A[i] & ~two & one)

Манипуляции с битами для рассчитанного two_ помогут решить проблему. Но, как вы упомянули

two_ = (A[i] & one) | (~A[i] & two)

Приведенное выше выражение можно легко получить, используя K-map, учитывая, что не имеет значения, то есть X для всех случаев, упомянутых выше, так как рассмотрение X не повлияет наше решение.

С учетом two_ и с учетом X
Это значение равно 1 для двух случаев, т. е. 3-го и 6-го, и X для двух случаев, т. е. 4-го и 8-й случай. Теперь рассмотрим minterms.

two_ = (~A[i] & two & ~one) | (A[i] & ~two & one) |  (~A[i] & two & one) | (A[i] & two & one)

Теперь, взяв общие (A и один) и (~A и два) в приведенном выше выражении, вы получите (два | ~ два) и (один | ~ один), что равно 1. Итак, мы будем остался с

two_ = (A[i] & one) | (~A[i] & two)

Для получения дополнительной информации!

Есть три статуса: 0, 1, 2

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

Вот логика:

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

x=0 00 01 10

x=1 01 10 00

высокий является функцией как высокого, так и низкого.

Если низкий == 1, то высокий = x, иначе высокий = высокий и ~ x

У нас есть

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

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

Точно так же у нас есть низкий уровень как функция как высокого, так и низкого:

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

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

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;
}

Первое, что пришло мне в голову, это больше, но проще для понимания. Просто реализуйте дополнительный мод на 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;
        }
    };

*