Single Number I II III

一系列關于位操作的問題。

• Single Number I II III
  • Single Number
  • Single Number II
  • Single Number III

Single Number

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?

Given [1,2,2,1,3,4,3], return 4

Leetcode:136. Single Number

Lintcode:82. Single Number

本題要求在指定數組中找出隻出現一次的元素，其中該數組有 2n+1 個元素且除要找出元素外均隻出現兩次。

還知道異或運算有如下特性：

⊕	1
1
1	1

即在 A⊕B 時,若有 A=B ,則 A⊕B=0 。

又知 A⊕B=B⊕A ,即滿足交換律。

可知， A1⊕A2⊕⋯⊕An=B ,其中 B 為隻出現一次的元素。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = ;
        for (int a : nums) {
            res ^= a;
        }
        return res;
    }
};
           

Single Number II

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

Note:

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

Given [1,1,2,3,3,3,2,2,4,1] return 4

Leetcode:137. Single Number II

Lintcode:83. Single Number II

本題是上一題的加強版，很顯然不再是一道可以用異或簡單求得答案的題了。

但是，仍可以使用二進制位的思想。

這一回将所有整數看做二進制數，則每一位有兩種可能 0 或 1

題中數組除要找到的元素隻出現一次外，其他元素均恰好出現3次。

是以，隻要記錄在整個數組中整數各位的數值就可以得到隻出現一次的整數的二進制位數分布情況。

num	8	7	6	5	4	3	2	1
7	1	1	1
7	1	1	1
7	1	1	1
2	1
sum	3	4	3
mod3 0 0 0 0 0 0 1 0 class Solution { public: int singleNumber(vector<int>& nums) { vector<int> bits(sizeof(int) * , ); for (int a : nums) { for (int i = ; i < bits.size() ; i ++) { bits[i] += (a & ); a >>= ; } } int res = ; for (int i = bits.size() - ; i >= ; i --) { res <<= ; res |= (bits[i] % ); } return res; } }; Single Number III Given an array of numbers 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. For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5]. Note: 1. The order of the result is not important. So in the above example, [5, 3] is also correct. 2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity? 本題是第一題的變種，與第二題關聯不大。要使其被歸化為問題一需要對數組進行分化。 這也是本題的關鍵。 能很明顯地看出單純的對數組進行異或，會得到目标數 A 和B的異或 A⊕B 這個數的二進制數中的 1 代表了A和 B 中其中一個在該位上為 0 另一個在該位上為 1 這樣就可以用該數的任意一個含 1 位來區分 A 和B 同時，又知由于其他元素恰好出現兩次。這些元素在上述的那個二進制位上也有 0 和1兩種情況，即用該位分劃也會将無關元素分為兩組。 但是，這并不會将某一進制素出現的兩次分到不同組中。 是以，至此可以确定，通過 A⊕B 在二進制表示中一個帶 1 的位，可以将數組分成兩個問題一中的數組。 在這裡為了快速地得到為 1 的位，我們采用将diff 和 -diff做與操作（這裡都使用補碼表示） 這裡利用了補碼取負時從後向前數的第一個不為 0 的數不會變得特性，取得了diff中第一個不為 0 的位。 num 8 7 6 5 4 3 2 1 7 1 1 1 -7 1 1 1 1 1 1 and 1 class Solution { public: vector<int> singleNumber(vector<int>& nums) { int diff = ; for (int a : nums) { diff ^= a; } diff &= -diff; //得到diff中一個二進制為一的位 vector<int> res( , ); for (int a : nums) { if ((a & diff) == ) //被分到在該位為0的一組 res[] ^= a; else //被分到在該位為1的一組 res[] ^= a; } return res; } };