leetcode 137
题目描述:
给定一个数组,数组中只有一个数字只出现一次,其余的数字出现三次,求这个只出现一次的数字。
输入:一个整型数组
输出:一个只出现一次的数字
题目限制:
使用线性时间复杂度,常量额外空间
思路:
1.自己在思考的时候很自然想到先对数组排序,然后一次判断前后中三个数是否相等,不相等则中间的数就是要求的只出现一次的数。但是 时间复杂度明显是O(nlogn),不符合要求。 我的思路代码:
public int singleNumber1(int[] nums) {
if (nums == null || nums.length == ) {
return ;
}
Arrays.sort(nums);
int i;
for (i = ; i < nums.length; i++) {
if (nums[i]!=nums[i]&&nums[i]!=nums[i+]) {
break;
}
}
System.out.println(nums[i]);
return nums[i];
}
2.在网上看见了一个大神的解题思路。叹为观止!基本思路是一个int数字有32位,对于二进制32位中的每一位计算“1”出现的次数只和,如果能被三整除说明只出现一次的那个数的二进制在该位也为0.如果不能被整除说明只出现一次的数的二进制数在该位是“1”,再采用左移的方式还原该位,最后使用或操作“|”将结果正确求出。 大神思路代码:
public int singleNumber(int[] nums) {
if (nums == null || nums.length == ) {
return ;
}
int res = ;
int sum = ;
for (int i = ; i < ; i++) {
sum = ;
for (int num : nums) {
int tmp = (num >> i) & ;
sum += (num >> i) & ;
}
if (sum % != ) {
res |= << i;
}
}
System.out.println(res);
return res;
}
重点
num>>i就是数字右移i位,然后与1做与运算,得出移位后最后一位是否为“1”。
如果sum不能被3整除,即 sum % 3 != 0, 则要求的数的二进制在该位为“1”。所以需要res |= 1 << i来还原。
扩展:
如果是类似的题,只是一个出现一次,一个出现n次,可以利用相同的解法,在整除的时候更改数字即可。
zsjwish
2018年4月22日13:52:22