|
1
2
3
4
5
6
|
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
|
题意：一个数组中的元素都出现了两次，只有俩数字出现了一次！！！！找出来！！！！！！
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
public
class
Solution {
public
int
[] singleNumber(
int
[] nums) {
int
[] ret=
new
int
[
2
];
if
(nums==
null
|| nums.length<
4
)
return
nums;
int
norresult=
0
;
for
(
int
i=
0
;i<nums.length;i++){
norresult^=nums[i];
}
///找到1的索引位置
int
indexof1=index1(norresult);
for
(
int
i=
0
;i<nums.length;i++){
if
(is1(nums[i],indexof1)==
1
){
////一个只与是1的做异或
ret[
0
]^=nums[i];
}
}
ret[
1
]=norresult^ret[
0
];
return
ret;
}
public
static
int
is1(
int
num,
int
index){
////判断第index位是不是1
num=num>>index;
return
num&
1
;
}
public
static
int
index1(
int
num){
/////判断第几位是1
int
index=
0
;
while
((num&
1
)==
0
){
num=num>>
1
;
index++;
}
return
index;
}
}
|
PS：这个可以参考single number1 的异或思想。不过此时需要分成两部分来找了。参见剑指offer。
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1908502
