Java for LeetCode 137 Single Number II

浏览数：223 / 时间：2015年06月08日

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?

解题思路一：

一个int的长度是32，因此可以开一个长度为32的数组，表示nums中所有元素各位1的个数和，然后%3即可得到结果。

JAVA实现如下：

	public int singleNumber(int[] nums) {
		int[] bitnum = new int[32];
		int res = 0;
		for (int i = 0; i < 32; i++) {
			for (int j = 0; j < nums.length; j++)
				bitnum[i] += (nums[j] >> i) & 1;
			res += (bitnum[i] % 3) << i;
		}
		return res;
	}

解题思路二：

分别用三个变量bit0、bit1、bit2表示nums元素中1个数为0、1、2的分布，最后返回bit1即可，JAVA实现如下：

	public int singleNumber(int[] nums) {
		int bit0 = ~0, bit1 = 0, bit2 = 0, oldTwo;
		for (int i = 0; i < nums.length; i++) {
			oldTwo = bit2;
			bit2 = (bit1 & nums[i]) | (bit2 & ~nums[i]);
			bit1 = (bit0 & nums[i]) | (bit1 & ~nums[i]);
			bit0 = (oldTwo & nums[i]) | (bit0 & ~nums[i]);
		}
		return bit1;
	}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java for LeetCode 137 Single Number II