作者:whisper
链接:https://www.proprogrammar.com/article/870
声明:请尊重原作者的劳动,如需转载请注明出处
一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
示例 1:
输入:nums = [4,1,4,6] 输出:[1,6] 或 [6,1]
示例 2:
输入:nums = [1,2,10,4,1,4,3,3] 输出:[2,10] 或 [10,2]
难度:中等;标签:无;编程语言:JAVA
无,当时位运算不行,这题不会
public int[] singleNumbers(int[] nums) {
int ret = 0;
for (int n : nums) {
ret ^= n;
}
int div = 1;
while ((div & ret) == 0) {
div <<= 1;
}
int a = 0, b = 0;
for (int n : nums) {
if ((div & n) != 0) {
a ^= n;
} else {
b ^= n;
}
}
return new int[]{a, b};
}
这个不看题解也很难懂,位运算很难(数学,字符串,图,动态规划等都很难),下面是官方题解
先考虑只有一个数字只出现一次,其它出现两次,这是容易做的,然后本题把所有数分成两组,每组中只有一个数出现一次,其它出现两次,如何把两个只出现一次的数分到两组中呢,两个不同的数必然某一位数字不同,找到不同的位,按这一位分组,如两个数是a和b,他们^的结果是所有数异或的结果x, 即x = a^b=a^b^...^nums[i]^...nums[len-1],由^的性质,如果某位不同,那么异或结果为1,通过这点找到最低不同的位,根据这一位分组就可以了,其它的数会两两相同被分到一组中(&和^还是很好用的)
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202205 | 1 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论