只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

1.位运算

1
2
3
4
5
6
7
8
9
10
11
//异或运算 ^=
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            ans ^= nums[i];
        }
        return ans;
    }
};
  1. 0 ^ x = x
  2. x ^ x = 0
  3. 异或满足交换律

2.暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//暴力双层for循环 ---- 超出时间限制
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            int flag = 1;
            for (int j = 0; j < nums.size(); ++j) {
                if (nums[j] == nums[i] && i != j) flag = 0; 
            }
            if (flag) return nums[i];
        }
        return -1;
    }
};

3.常见位运算的操作

  • 得到右数第 k 位值：(x >> k) & 1
  • 把右数第 k 位值置1：x | (1 << k)
  • 把右数第 k 位值取反：x ^ (1 << k)
  • 把最右边的1置0：x & (x - 1)
  • 把最右边的0置1：x | (x + 1)
  • 判断奇偶（最低位）：x & 1