[LeetCode] 137. Single Number II 單獨(dú)的數(shù)字之二

Given a non-empty 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?

Example 1:

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

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

這道題是之前那道 Single Number 的延伸，那道題的解法就比較獨(dú)特，是利用計(jì)算機(jī)按位儲(chǔ)存數(shù)字的特性來做的，這道題就是除了一個(gè)單獨(dú)的數(shù)字之外，數(shù)組中其他的數(shù)字都出現(xiàn)了三次，還是要利用位操作 Bit Manipulation 來解?？梢越⒁粋€(gè) 32 位的數(shù)字，來統(tǒng)計(jì)每一位上1出現(xiàn)的個(gè)數(shù)，如果某一位上為1的話，那么如果該整數(shù)出現(xiàn)了三次，對(duì)3取余為0，這樣把每個(gè)數(shù)的對(duì)應(yīng)位都加起來對(duì)3取余，最終剩下來的那個(gè)數(shù)就是單獨(dú)的數(shù)字。代碼如下：

解法一：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int j = 0; j < nums.size(); ++j) {
                sum += (nums[j] >> i) & 1;
            }
            res |= (sum % 3) << i;
        }
        return res;
    }
};

還有一種解法，思路很相似，用3個(gè)整數(shù)來表示 INT 的各位的出現(xiàn)次數(shù)情況，one 表示出現(xiàn)了1次，two 表示出現(xiàn)了2次。當(dāng)出現(xiàn)3次的時(shí)候該位清零。最后答案就是one的值。

1. ones   代表第 ith 位只出現(xiàn)一次的掩碼變量
2. twos  代表第 ith 位只出現(xiàn)兩次次的掩碼變量
3. threes  代表第 ith 位只出現(xiàn)三次的掩碼變量

假設(shè)現(xiàn)在有一個(gè)數(shù)字1，更新 one 的方法就是 ‘亦或' 這個(gè)1，則 one 就變成了1，而 two 的更新方法是用上一個(gè)狀態(tài)下的 one 去 ‘與' 上數(shù)字1，然后 ‘或' 上這個(gè)結(jié)果，這樣假如之前 one 是1，那么此時(shí) two 也會(huì)變成1，這 make sense，因?yàn)檎f明是當(dāng)前位遇到兩個(gè)1了；反之如果之前 one 是0，那么現(xiàn)在 two 也就是0。注意更新的順序是先更新 two，再更新 one，不理解的話只要帶個(gè)只有一個(gè)數(shù)字1的輸入數(shù)組看一下就不難理解了。然后更新 three，如果此時(shí) one 和 two 都是1了，由于先更新的 two，再更新的 one，two 為1，說明此時(shí)至少有兩個(gè)數(shù)字1了，而此時(shí) one 為1，說明了此時(shí)已經(jīng)有了三個(gè)數(shù)字1，這塊要仔細(xì)想清楚，因?yàn)?one 是要 ‘亦或' 一個(gè)1的，值能為1，說明之前 one 為0，實(shí)際情況是，當(dāng)?shù)诙€(gè)1來的時(shí)候，two 先更新為1，此時(shí) one 再更新為0，下面 three 就是0了，那么 ‘與' 上t hree 的相反數(shù)1不會(huì)改變 one 和 two 的值；那么當(dāng)?shù)谌齻€(gè)1來的時(shí)候，two 還是1，此時(shí) one 就更新為1了，那么 three 就更新為1了，此時(shí)就要清空 one 和 two 了，讓它們 ‘與' 上 three 的相反數(shù)0即可，最終結(jié)果將會(huì)保存在 one 中，參見代碼如下：

解法二：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < nums.size(); ++i) {
            two |= one & nums[i];
            one ^= nums[i];
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }
};

下面這種解法思路也十分巧妙，根據(jù)上面解法的思路，我們把數(shù)組中數(shù)字的每一位累加起來對(duì)3取余，剩下的結(jié)果就是那個(gè)單獨(dú)數(shù)組該位上的數(shù)字，由于累加的過程都要對(duì)3取余，那么每一位上累加的過程就是 0->1->2->0，換成二進(jìn)制的表示為 00->01->10->00，可以寫出對(duì)應(yīng)關(guān)系：

00 (+) 1 = 01

01 (+) 1 = 10

10 (+) 1 = 00 ( mod 3)

用 ab 來表示開始的狀態(tài)，對(duì)于加1操作后，得到的新狀態(tài)的 ab 的算法如下：

b = b xor r & ~a;

a = a xor r & ~b;

這里的 ab 就是上面的三種狀態(tài) 00，01，10 的十位和各位，剛開始的時(shí)候，a和b都是0，當(dāng)此時(shí)遇到數(shù)字1的時(shí)候，b更新為1，a更新為0，就是 01 的狀態(tài)；再次遇到1的時(shí)候，b更新為0，a更新為1，就是 10 的狀態(tài)；再次遇到1的時(shí)候，b更新為0，a更新為0，就是 00 的狀態(tài)，相當(dāng)于重置了；最后的結(jié)果保存在b中，明白了上面的分析過程，就能寫出代碼如下；

解法三：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.size(); ++i) {
            b = (b ^ nums[i]) & ~a;
            a = (a ^ nums[i]) & ~b;
        }
        return b;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(137.單獨(dú)的數(shù)字之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)單獨(dú)的數(shù)字之二內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論