LeetCode——single-number系列

LeetCode——single-number系列

Question 1

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution

这个题的求解用到了按位异或的操作，因为两个相同的数异或是为0的，然后按位操作又满足交换律，所以一直异或下去就能得到单独的一个数字，这有点像模拟二进制求和。

class Solution {

public:

    int singleNumber(int A[], int n) {

        int sum = 0;

        for (int i = 0; i < n; i++) {

        	sum ^= A[i];

        }

        return sum;

    }

};

进阶版本

Question 2

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution

要是如果有三进制的操作，那么这道题就很简单了，那么我们需要模拟三进制的操作，ones表示一个1的个数，twos表示两个1的个数，ones&twos结果表示三个1的个数。

class Solution {

public:

    int singleNumber(int A[], int n) {

       int ones = 0;

       int twos = 0;

       int threes;

       for (int i = 0; i < n; i++) {

           int t = A[i];

           twos |= ones & t;      // 或表示加，与表示求两个1的个数

           ones ^= t;             // 异或操作表示统计一个1的个数

           threes = ones & twos;  // 与表示三个1的个数

           ones &= ~threes;

           twos &= ~threes;

       }

       return ones;

    }

};

还有一种用额外存储空间的解法，统计每一位1的个数。

class Solution {

public:

    int singleNumber(int A[], int n) {

        int bitSum[32] = {0};

        for (int i = 0; i < n; i++) {

            int mask = 0x1;

            for (int j = 0; j < 32; j++) {

                int bit = A[i] & mask;

                if (bit != 0)

                    bitSum[j] += 1;

                mask = mask << 1;

            }

        }

        int res = 0;

        for (int i = 31; i >= 0; i--) {

            res = res << 1;

            res += (bitSum[i] % 3);

        }

        return res;

    }

};