Single Number

原題鏈接Single Number

一個(gè)整數(shù)序列，每個(gè)數(shù)字都出現(xiàn)兩次只有一次數(shù)字出現(xiàn)了一次，找到只出現(xiàn)一次的那個(gè)數(shù)字

位運(yùn)算的異或算法有如下幾個(gè)性質(zhì)

• 值相同的兩個(gè)數(shù)字異或結(jié)果為0，即a ^ a = 0
• 交換律，即a ^ b = b ^ a
• 綜上兩條性質(zhì)，得到a ^ b ^ b = b ^ a ^ b = b ^ b ^ a = a

所以只需要遍歷一遍序列，并做異或運(yùn)算，所有出現(xiàn)兩次的數(shù)字在異或的過程中都變?yōu)?，只留下唯一的一個(gè)出現(xiàn)一次的數(shù)字

代碼如下

class Solution { public:int singleNumber(vector<int>& nums) {return std::accumulate(nums.begin(), nums.end(), 0, bit_xor<int>()); } };

---

Single Number II

原題鏈接Single Number II

一個(gè)整數(shù)序列，每個(gè)數(shù)字都出現(xiàn)三次只有一個(gè)數(shù)字出現(xiàn)了一次(也可以出現(xiàn)一次或兩次)，找到這個(gè)數(shù)字

利用上面異或的思想，找到某種運(yùn)算使得三次計(jì)算結(jié)果后為0，一次和兩次的計(jì)算結(jié)果和數(shù)字本身相同，本質(zhì)上還是采用bitmap的思想

采用兩個(gè)整數(shù)變量a和b，如果a的某一位是1，代表目前為止這一位出現(xiàn)了1次，如果b的某一位是1，代表到目前為止這一位出現(xiàn)了2次，a和b對(duì)應(yīng)位置上都為0表示這一位出現(xiàn)了0次或3次(因?yàn)樾枰ＷC三次運(yùn)算結(jié)果為0)

僅僅觀察一位的話，有如下的轉(zhuǎn)換關(guān)系，其中c是當(dāng)前遍歷到的數(shù)字的對(duì)應(yīng)位，a’和b’是更新后的a和b

abca’b’

0	0	0	0	0
0	0	1	1	0
1	0	0	1	0
1	0	1	0	1
0	1	0	0	1
0	1	1	0	0

找到a’和b’的運(yùn)算式子，即將a’為1和b’為1的情況分離出來

abca’

0	0	1	1
1	0	0	1

abcb’

1	0	1	1
0	1	0	1

得到運(yùn)算式

a' = ((~a) & (~b) & c) | (a & (~b) & (~c)); b' = (a & (~b) & c) | ((~a) & b & (~c));

最后，a’表示出現(xiàn)一次的數(shù)字，b’表示出現(xiàn)兩次的數(shù)字

代碼如下

class Solution { public:int singleNumber(vector<int>& nums) {int a = 0, b = 0;for(auto& c : nums){int tmpa = ((~a) & (~b) & c) | (a & (~b) & (~c));int tmpb = (a & (~b) & c) | ((~a) & b & (~c));a = tmpa;b = tmpb;}return a | b;} };

---

Single Number III

原題鏈接Single Number III

一個(gè)整數(shù)序列，每個(gè)數(shù)字都出現(xiàn)了兩次只有兩個(gè)數(shù)字出現(xiàn)了一次，找到這兩個(gè)數(shù)字

兩個(gè)出現(xiàn)一次的數(shù)字不能簡(jiǎn)單的使用異或找到，但是考慮一下，假設(shè)a, b分別是這兩個(gè)只出現(xiàn)一次的數(shù)字，c1, c2, …, cn代表其他的數(shù)字，那么

a, c1, c2, …, cn這個(gè)序列可以采用問題一的解法求得a(異或一遍)

b, c1, c2, …, cn這個(gè)序列同樣可以采用問題一的解法

但是要怎樣分離出a和b呢，如果最開始異或一遍整數(shù)序列，那么得到的結(jié)果就是a ^ b的值，由于a和b肯定不相等，那么a ^ b != 0，這就會(huì)導(dǎo)致結(jié)果中肯定有一位是1，哪一位都可以，不過最好找的是最右邊的1，即

int diff = a ^ b; diff = (diff) & (~(diff - 1));

此時(shí)diff只有一位是1，且這一位的1是整個(gè)diff中最右邊的1。那么就可以采用這個(gè)diff區(qū)分a和b，因?yàn)閍和b一定有一個(gè)該位是1，有一個(gè)該位是0，才可以在異或結(jié)果中使得該位是1

剩下的工作仍然是異或一遍序列即可，代碼如下

class Solution { public:vector<int> singleNumber(vector<int>& nums) {vector<int> res{0, 0};int diff = std::accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());diff = (diff) & (~(diff - 1));for(auto& num : nums){/* 這里無需考慮其他數(shù)字與diff的異或結(jié)果，因?yàn)樗麄兌际浅蓪?duì)出現(xiàn)的，異或不異或都無所謂 */if(diff ^ num == 0){res[0] ^= num;}else{res[1] ^= nums;}}return res;} };

---

這三道題主要考察的是對(duì)位運(yùn)算的掌握，尤其是位操作，本質(zhì)上是bitmap思想，用每一位表示出現(xiàn)的情況

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的每天一道LeetCode-----一个整数序列，每个元素出现两次，只有一个(两个)出现一次，找到这个(这两个)元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。