136/137/260-只出现1次的数字

LeetCode 136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

method: 异或

• a ^ a = 0
• 0 ^ a = a

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (auto n : nums) res ^= n;
    return res;
}

---

LeetCode 137. Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

method

除了一个数外，其他数都出现了3次，找出这个数

遍历每个数的每一个Bit，如果出现了3次，累加之后模以3应该是0，否则就是多出来的那个数的原因，所以将模以3的结果记录下来，一位一位填充res

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        int sum = 0;
        for (auto n : nums) {
            sum += (n >> i) & 1;    // 累加第i位的值
        }
        if (sum % 3) res += (1 << i);   // 第i位多出来了，就加上
    }
    return res;
}

---

LeetCode 260. Single Number III

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

method

除了两个数a和b外，其他数都出现了2次

全部异或可以消掉其他数，但a和b也会异或，分不清楚了
可以在全部异或的结果中找最低位的1的bit，这个1一定是a或者b引起的，然后再遍历数组，将bit位置为1的数全部异或起来，这样就可以找出a或b，然后又全体异或的结果推出另一个数

vector<int> singleNumber(vector<int>& nums) {
    int s1 = 0;
    for (auto n : nums) s1 ^= n;    // 全体异或
    
    int k = 0;
    while (!(s1 >> k & 1)) k++; // 找出最低位的1
    
    int s2 = 0;
    for (auto n : nums) {
        if (n >> k & 1) s2 ^= n;    // 将第k位为1的数异或起来，就可以找出其中一个数
    }
    return vector<int>({s2, s1 ^ s2});
}