809
[LeetCode]*137.Single Number II
【題目】
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
【題意】
給定一個整數數組，每個元素出現了三次，除了一個。找出那個出現一次的數字。
注意：
你的算法應該在一個線性時間複雜度完成。你能不能無需使用額外的內存來完成它？
【思路一】
所有的數用二進製表示，我們把每個數的第i 位取和之後再對3取餘，那麼隻會有兩個結果 0 或 1 。 如果為0代表隻出現一次的那個數第i位也為0，
如果為1表示隻出現一次的那個數第i位也為1。因此取餘的結果就是那個 “Single Number”。
下麵是一個直接用大小為 32的數組來記錄所有 位上的和。
【代碼一】
/*---------------------------------------
* 日期：2015-04-26
* 作者：SJF0115
* 題目: 137.Single Number II
* 網址：https://leetcode.com/problems/single-number-ii/
* 結果：AC
* 來源：LeetCode
* 博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int singleNumber(int A[], int n) {
int count[32] = {0};
int result = 0;
for(int i = 0;i < 32;++i){
for(int j = 0;j < n;++j){
if ((A[j] >> i) & 1) {
++count[i];
}//if
}//for
result |= ((count[i] % 3) << i);
}//for
return result;
}
};
int main(){
Solution solution;
int A[] = {2,3,4,2,5,2,3,3,5,5};
int result = solution.singleNumber(A,10);
// 輸出
cout<<result<<endl;
return 0;
}
【思路二】
這個算法是有改進的空間的，可以使用掩碼變量
方法 2：用 ones 記錄到當前處理的元素為止，二進製 1 出現“1 次”（mod 3 之後的 1）的有哪些二進製位；
用 twos 記錄到當前計算的變量為止，二進製 1 出現“2 次”（mod 3 之後的 2）的有哪些二進製位。
當 ones 和 twos 中的某一位同時為 1 時表示該二進製位上 1 出現了 3 次，此時需要清零。
即用二進製模擬三進製運算。最終 ones 記錄的是最終結果。
【代碼二】
/*---------------------------------------
* 日期：2015-04-26
* 作者：SJF0115
* 題目: 137.Single Number II
* 網址：https://leetcode.com/problems/single-number-ii/
* 結果：AC
* 來源：LeetCode
* 博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int singleNumber(int A[], int n) {
int ones = 0, twos = 0, threes = 0;
for(int i = 0;i < n;++i){
// 出現2次
twos |= (ones & A[i]);
// 出現1次
ones ^= A[i];
// 當ones和twos中的某一位同時為1時表示該二進製位上1出現了3次
threes = ones & twos;
// 二進製位上1出現了3次此時ones和twos對應位上清零
ones &= ~threes;
twos &= ~threes;
}//for
return ones;
}
};
int main(){
Solution solution;
int A[] = {2,3,4,2,5,2,3,3,5,5};
int result = solution.singleNumber(A,10);
// 輸出
cout<<result<<endl;
return 0;
}
最後更新：2017-04-03 12:54:49