class Solution {
public int singleNumber(int[] nums) {
int one = 0 ,two = 0;
for (int i=0 ; i < nums.length ; i++)
{
//更新第一位
// if (two == 0)
// one = one ^ n;
// if (two == 1)
// one = 0;
one = ( one ^ nums[i] ) & ~two;
//更新第二位
// if (one == 0)
// two ^= n;
// if (one == 1)
// two = 0;
two = ( two ^ nums[i] )& ~one;
}
return one;
}
}
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = 0, two = 0;
for(int x : nums){
one = one ^ x & ~two;
two = two ^ x & ~one;
}
return one;
}
};
class Solution {
public int singleNumber(int[] nums) {
int[] res = new int[32];
int n = nums.length;
int m = 1;
int sum = 0;
for(int i=0;i<32;i++) {
for(int j=0;j<n;j++) {
if((nums[j]&m)!=0) {
res[i]++;
}
}
res[i] = res[i]%3;
sum = sum+res[i]*m;
m = m<<1;
}
return sum;
}
}
class Solution {
public int singleNumber(int[] nums) {
// 统计每一位1的个数，再%3
// 结果为0，则x那位为0，结果为1，则那位结果为1
int[] count = new int[32];
int x = 0;
int m=1;
for(int i=0;i<32;i++){
for(int j=0;j<nums.length;j++){
if((m&nums[j])!=0) count[i]++;
}
count[i] %=3;
// m = 2^i
if(count[i]!=0) x += m;
m<<=1;
}
return x;
}
}
class Solution {
public int singleNumber(int[] nums) {
int [] res = new int[32];
int m = 1;
int sum = 0;
for(int i = 0; i < 32; i++){
for(int j = 0; j < nums.length; j++){
if((nums[j] & m)!= 0){
res[i]++;
}
}
res[i] = res[i] % 3;
sum = sum + res[i] * m;
m = m << 1;
}
return sum;
//时间复杂度： O(n)
//空间复杂度： O(1)
}
}
class Solution {
public:
vector singleNumbers(vector& nums) {
int z = 0;
for(int i = 0;i < nums.size();++i){
z ^= nums[i];
}
int m = 1;
while((m & z) == 0){
m = m << 1;
}
int x = 0,y = 0;
for(int i = 0;i < nums.size();++i){
if((nums[i] & m) == 0){
x ^= nums[i];
}
else{
y ^= nums[i];
}
}
return vector{x,y};
}
};
func singleNumber(nums []int) int {
res := 0
for i := 0; i < 32; i++ {
//每一位
bit := 0
//对每一位求和
for _, v := range nums {
bit +=((v >> i) & 1)
}
//对3取余
res += ((bit%3) << i)
}
return res
}
class Solution {
public int singleNumber(int[] nums) {
int[] res = new int[32];
int m = 1, sum = 0;
for(int i = 0; i < 32; i ++) {
for(int j = 0; j < nums.length; j ++) {
if((nums[j] & m) != 0) {
res[i] ++;
}
}
res[i] %= 3;
sum += res[i] * m;
m <<= 1;
}
return sum;
}
}
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i = 0; i < 32; i++){
int count = 0;
for(int num : nums){
count += ((num >> i) & 1);//统计第 i 位 1 的个数
}
res += ((count % 3) << i);//当前位1的个数对3取余即为当前位置的值
}
return res;
}
}
shuaidi
共以下 16 个回答
“`c++代码& nums) {
class Solution {
public:
int singleNumber(vector
int n = nums.size();
sort(nums.begin(),nums.end());
for(int i=0;i
”’java
class Solution {
public int singleNumber(int[] nums) {
int[] counts = new int[32];
for(int num : nums){
for(int j = 0;j < 32;j++){
counts[j]+=num&1;
num>>>=1;
}
}
int res = 0,m = 3;
for(int i = 0;i < 32;i++){
res <<= 1;
res |= counts[31 – i] % m;
}
return res;
}
}
”’
时间复杂度O(N)
空间复杂度O(1)
c++ 代码& nums) & nums) & nums)
class Solution {
public:
int singleNumber(vector
{
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-2;i+=3)
if(nums[i]!=nums[i+2]) return nums[i];
return nums.back();
}
};
位运算
class Solution {
public:
int singleNumber(vector
{
int count[32]={0},s=0;
for(int i=0;i<nums.size();i++)
{
for(int j=0;j<32;j++)
{
count[j]+=nums[i]&1;
nums[i]>>=1;
}
}
for(int j=0;j<32;j++)
{
if(count[j]%3)
s+=pow(2,j);
}
return s;
}
};
有限自状态机
class Solution {
public:
int singleNumber(vector
{
int o=0.,t=0;
for(int i=0;i<nums.size();i++)
o=o^nums[i]&~t,t=t^nums[i]&~o;
return o;
}
};
时间复杂度：O（n）
空间复杂度：O（1）
时间复杂度：O（n）
空间复杂度：O（1）
7.25
Day17：下面是代码
代码
没接触过根本想不到啊，主要是异或操作，另外找到第一个不同位置然后将数组分成两组的操作也很巧妙。
以上是代码
统计所有数字在各二进制位上1的个数，并对3取余，最终结果即为数组中出现次数为1的数