p260

发表于 | 分类于 |

LeetCode 260 Single Number III 题解

1.题目：

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].

题意：

输入一个数组，这个数组中除了两个数之外其他的数都两两对应，找出这两个没有对应的数

2.解题思路:

思路是这样的，先用亦或的位运算，将两两相同的抵消掉，然后留下这两个数的亦或结果。即a^b。
分析这个结果 all=a^b 即如果某位为1，则这一位上a,b的二进制表达不同。所以先取出为1的某一位。然后将数组分成两类，这里介绍下Integer.highestOneBit(x),
具体用法见代码。再对分成两类的数组分别亦或，得到a,b。

3.代码

[title] [] [url] [link text]
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
package leetcode;

import java.util.Scanner;

public class p260 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String a = in.nextLine();

		int[] nn1 = new int[(a.length() + 1) / 2];
		String[] n1 = a.split(" ");

		for (int i = 0; i < (a.length() + 1) / 2; i++) {
			nn1[i] = Integer.parseInt(n1[i]);
			// System.out.println(nn1[i]);
		}

		// 完成数据的输入并进行处理
		int ans[] = new int[2];
		ans = singleNumber(nn1);
		for (int i = 0; i < ans.length; i++) {
			System.out.print(ans[i] + " ");
		}

	}

	public static int[] singleNumber(int[] nums) {
		int ans[] = { 0, 0 };

		int all = 0;
		for (int i : nums) {
			all = i ^ all;
		}
		int allmax = Integer.highestOneBit(all);
		// 只将最高位中的1留下，得到这个数
		// 如7为111 变为100=4，即获取不大于这个数的最小的2的n次方
		for (int i : nums) {
			// 最高位为0
			if ((i & allmax) == 0) {
				ans[0] ^= i;
			}
			// 最高位为1
			else {
				ans[1] ^= i;
			}
		}
		return ans;
	}

}



4.一些总结：

想了好久(捂脸)，然后看提示跟自己想的差不多是用位运算。。然还是想不出。看别人代码并不太懂。。最后花了几天终于理清了TUT