本文主要是介绍[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}//forresult |= ((count[i] % 3) << i);}//forreturn 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;}//forreturn 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;
}
这篇关于[LeetCode]*137.Single Number II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
