LeetCode260——只出现一次的数字III
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/single-number-iii/description/
题目描述:
知识点:位运算
思路:位运算
假设两个只出现一次的元素分别是num1和num2,按照LeetCode136——只出现一次的数字中的思路,我们很容易得到num1 ^ num2的结果num1XORNum2。将num1XORNum2表示成二进制数的形式,其中为1的位说明num1和num2的该位的值是不相同的。我们取num1XORNum2二进制数形式的最右边的那个1,而其余位均置0,用这个数来将原数组nums中的元素分成两种类型:
(1)该位是1。
(2)该位是0。
由于num1和num2的该位的值是不相同的,这样的分类显然将num1和num2分别放进了上述两种分类中。这时候我们再采用LeetCode136——只出现一次的数字中的思路遍历一次nums数组即可。
时间复杂度是O(n)。空间复杂度是O(1)。
JAVA代码:
public class Solution {
public int[] singleNumber(int[] nums) {
int num1XORNum2 = 0;
for (int i = 0; i < nums.length; i++) {
num1XORNum2 ^= nums[i];
}
num1XORNum2 &= -num1XORNum2;
int[] result = new int[2];
result[0] = result[1] = 0;
for (int i = 0; i < nums.length; i++) {
if(0 == (nums[i] & num1XORNum2)){
result[0] ^= nums[i];
}else{
result[1] ^= nums[i];
}
}
return result;
}
}
LeetCode解题报告: