装饰行业网站建设方案,有限责任公司和股份有限公司,中国建设银银行招聘网站,上海seo推广方法2018-06-17 14:04:27 问题描述#xff1a; 问题求解#xff1a; 方法一、如果对空间复杂度没有要求#xff0c;那么直接使用HashMap对每个数字出现次数进行计数#xff0c;最后对HashMap遍历一遍即可#xff0c;总的时间复杂度为O(n)#xff0c;空间开销较大。 方法二、对…2018-06-17 14:04:27 问题描述 问题求解 方法一、如果对空间复杂度没有要求那么直接使用HashMap对每个数字出现次数进行计数最后对HashMap遍历一遍即可总的时间复杂度为O(n)空间开销较大。 方法二、对空间要求比较严格的话那就只能使用位运算了一个简明的思路是对于所有出现三次的数其各个位置上1出现的次数也是3的倍数可以利用这点来进行判断。 public class SingleNumberII {public int singleNumber(int[] nums) {int res 0;for (int i 0; i 32; i) {int mask 1;int cnt 0;mask mask i;for (int j 0; j nums.length; j) {if ((nums[j] mask) ! 0) cnt;}if (cnt % 3 ! 0) res | mask;}return res;}
}方法三、上面的解法系数较大可以进一步对其简化。核心思路依然是位运算这里引入两个变量ones 和 twos。ones:记录到当前计算的变量为止二进制1出现“1次”mod 3 之后的 1的数位。 twos:记录到当前计算的变量为止二进制1出现“2次”mod 3 之后的 2的数位。 当ones和twos中的某一位同时为1时表示二进制1出现3次此时需要清零。即用二进制模拟三进制计算。最终ones记录的是最终结果。 public int singleNumberII(int[] nums) {int ones 0;int twos 0;int xthree 0;for (int num : nums) {twos | (ones num);ones ^ num;xthree ~(twos ones);ones xthree;twos xthree;}return ones;}转载于:https://www.cnblogs.com/TIMHY/p/9192819.html
