p137

发表于 | 分类于 |

LeetCode 137 Single Number II 题解

1.题目：

Given an array of integers, every element appears three times except for one. Find that single one.

题意：

输入一个数组，除了某个数，其他数都出现了三次，输出这个数。

2.解题思路:

正常解法，排序遍历找出特殊数。
位运算解法：如下
遍历32位的每一位，如果这个位上有值则累加，最后累加值对三取余
清除掉出现三次的数。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 

public class Solution {
    public int singleNumber(int[] nums) {
      int ans = 0;
		for (int i = 0; i < 32; i++) {

			int count = 0;
			for (int n : nums) {
				int val = (n >> i) & 1;
				if (val == 1) {
					count++;
					count = count % 3;//出现3次清零
				}
				// System.out.println(n+"  "+val);

			}
			if (count != 0) {
				ans = ans | (count << i);//不为0则把它放到相应的位置上
			}

		}
		return ans;
    }
}

4.一些总结：

ps:调试时注意移位以及负数。
扩展：其他数出现n次只要改count=count%n;就可以了~