## Friday, November 21, 2014

### [LeetCode] Single Number I, II

Single Number I

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

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?

 ```1 2 3 4 5 6 7 8 9``` ```class Solution { public: int singleNumber(int A[], int n) { int res = 0; for(int i=0; i

1110
1110
1110
1001
_____
4331    对每一位进行求和
1001    对每一位的和做%3运算，来消去所有重复3次的数

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16``` ```class Solution { public: int singleNumber(int A[], int n) { int res = 0; for(int i=31; i>=0; i--) { int sum = 0; int mask = 1<

#### 1 comment:

1. Here is another solution
public class Solution {
public int singleNumber(int[] nums) {
int p = 0;
int q = 0;
for(int i = 0; i<nums.length; i++){
p = q & (p ^ nums[i]);
q = p | (q ^ nums[i]);
}
return q;
}
}
Analysis from this blog post : http://traceformula.blogspot.com/2015/08/single-number-ii-how-to-come-up-with.html ﻿