LEET code-- 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?

Subscribe to see which companies asked this question

類似題目萬能解法:
把每個數字的bit各自加起來，在去除他要的需求

// e.g. , 5,5,5,2 - 101 101 101 010 - 313 - answer is 3%3,1%3,3%3 - 010

一開始忘記memset那邊要多乘sizeof(int)，而我要了32個int  不能只寫32.....

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

int singleNumber(int* nums, int numsSize) { int bit[32]; memset(bit,0,32*sizeof(int)); for(int i=0;i<32;i++){ for(int j =0;j<numsSize;j++){ if(nums[j]&(1<<i))bit[i]++; } } int ret=0; for(int i=0;i<32;i++){ if(bit[i]%3!=0){ ret+=(1<<i); } } return ret; }

----------------
更好的解法
不用再多一個for
反正每個bit跑完就去看他有沒有餘3  在or起來就好(不用考慮%3==0  反正or也會是0)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int singleNumber(int* nums, int numsSize) { int bit[32]; memset(bit,0,32*sizeof(int)); int ret=0; for(int i=0;i<32;i++){ for(int j =0;j<numsSize;j++){ if(nums[j]&(1<<i))bit[i]++; } if(bit[i]%3)ret=ret | (1<<i); } return ret; }

--------------
特紓解
一個for就可解完的神解釋
方式:
這題是每個都會重複三次  所以可以做成state machine
The solution use two bit (a,b) to represent the initial state:

• 00: appear 3n times
• 01: appear 3n+1 times
• 10: appear 3n+2 times

The target state can be easily deducted that we want:
if data incoming: 00 -> 01 ->10 -> 00 if no data incoming, no change.
As a result, we can calculate the table in ziyihao's post:

current   incoming  next
a b            c    a b
0 0            0    0 0
0 1            0    0 1
1 0            0    1 0
0 0            1    0 1
0 1            1    1 0
1 0            1    0 0

其中a代表出現兩次了，b代表出現1次了，c是下一次近來的bit
所以可以利用a b來做出類似XOR的功能  因為出現三次的都會被消掉

https://leetcode.com/discuss/54970/an-general-way-to-handle-all-this-sort-of-questions

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public class Solution { public int singleNumber(int[] nums) { //we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero. //#curent income ouput //# ab c/c ab/ab //# 00 1/0 01/00 //# 01 1/0 10/01 //# 10 1/0 00/10 // a=~abc+a~b~c; // b=~a~bc+~ab~c; int a=0; int b=0; for(int c:nums){ int ta=(~a&b&c)|(a&~b&~c); b=(~a&~b&c)|(~a&b&~c); a=ta; } //we need find the number that is 01,10 => 1, 00 => 0. return a|b; } }