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?

思路:

创建一个sizeof(int)长度的数组,count[sizeof(int)],count[i]表示在i位出现的1的次数。如果count[i]是3的倍数,则忽略;否则取出来组成result。

代码:

public class Solution {
public int singleNumber(int[] nums) {
final int W = Integer.SIZE;
int[] count = new int[W];
for (int i = 0; i < nums.length; i++){
for (int j = 0; j < W; j++){
count[j] += (nums[i] >> j) & 1;
}
}
int result = 0;
for (int i = 0; i < W; i++){
count[i] %= 3;
result += count[i] << i;
}
return result;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :