By

文章目录
  1. 1. 题目
  2. 2. 方法1
  3. 3. 方法2
  4. 4. 参考

题目

假设你有一个用 1001 个整数组成的数组,这些整数是任意排列的,但是你知道所有的整 数都在 1 到 1000(包括 1000)之间。此外,除一个数字出现两次外,其他所有数字只出现一 次。假设你只能对这个数组做一次处理,用一种算法找出重复的那个数字。如果你在运算中 使用了辅助的存储方式,那么你能找到不用这种方式的算法吗?

方法1

这里都说1~1000都至少包含一遍了，所以求和在减去1~1000的和即可
假设遍历数组之后的求和为sum，则那个数字就是sum-(1000*10001/2)

但是如果这里不是1000，而是这个数字非常的大，求和就可能出现溢出

方法2

还记得有一道经典的leetcode题目就是一个数组中每个数出现2次，只有一个数字出现了3次，找出这个数字。
该题目的思路是A^A=0,A^0=A

按这个思路，因为我们知道1~1000已经出现一遍了，那么在遍历的时候自变量i也会从1~1000出现一遍，所以可以利用i来构造每个数字出现两次的情况，所以解题思路就是

1
2
3
4
5
6
7
8
9
10
public static int searchTwiceNum(int a[])
{
	int k=a[0];
	for(int i=1;i<a.length;i++)
	{
		k^=a[i]^i;//通过i来构造
	}
	
	return k;
}

这样操作就不会出现溢出的情况了

参考

  • July微软面试题第8题

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 题目
  2. 2. 方法1
  3. 3. 方法2
  4. 4. 参考