Question:
Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
如果可以用辅助空间的话,可以用HashSet来处理,如果add失败说明有重复的。但是如果不能用额外空间的话呢?
Solution 1:
考虑加法。1+2+...+n = n(n-1)/2
假设数组所有元素之和为sum, 那么sum-n(n-1)/2就是我们要找的重复的数。
public int findDuplicate(int[] nums) { int sum = 0; int n = nums.length; int expected = n*(n-1)/2; for(int i=0; i<n; i++) { sum += nums[i]; } return sum-expected; }
但是数组的元素数达到或接近INT_MAX的时候, 加法运算就会溢出。我们还可以考虑位运算XOR。
XOR具有以下性质:
交换律:
结合律:
恒等律:
归零律:
自反:
假设给定数组A[6] = {5,2,3,4,3,1},而我们期望的数组应该为A[6]={0,1,2,3,4,5}。其中我们用0来代替重复的元素。
接下来对给定数组和我们期望数组的所有元素做异或运算:
(5^0)^(2^1)^(3^2)^(4^3)^(3^4)^(1^5)
= (5^5)^(2^2)^(3^3)^(4^4)^(1^1)^(3^0)
= 0^3
= 3
写成代码则非常简单。
Solution2:
public int findDuplicate(int[] nums) { int dup = 0; for(int i=0; i<nums.length; i++) { dup ^= nums[i]^i; } return dup; }
Reference:
相关推荐
PROJECT 02-02 Reducing the Number of Gray Levels in an Image (a) Write a computer program capable of reducing the ... 2.21(a) and duplicate the results shown in Fig. 2.21 of the book.(网络资源分享)
Different strategies for removing duplicate records in SQL Server
element in the array. //How can you sort an array and remove duplicate entries. A few questions on Big O efficiency. Questions on memory management. * //Implement a HashMap. Try to stick to the syntax...
2. Write a program that reads ten numbers supplied by the user into a 2 by 5 array, and then prints out the maximum and minimum values held in: (a) each row (2 rows) (b) the whole array 3.Use a...
Your Excel Survival Kit: Your Guide to Surviving and Thriving in an Excel world By 作者: Anne Walsh ...Identifying Duplicate Entries in a List Simple Normalization(Getting Crossways Data to Go
这款Manyprog Find Duplicate Files软件功能强大全面,简单易操作,使用后可以帮助用户更轻松快捷的查找并删除重复文件。软件可以帮助用户查找计算机上的重复文件,并根据需要进行清理,非常的方便,还能节省存储...
5. Distribute Vistanita Duplicate Finder in any other form than in the official distribution packages without a written permission from the Author. 6. Use the licensed version of Vistanita Duplicate ...
FindDuplicate 简单HTML游戏可查找重复项 号码 日语字符 希腊字符 表情符号
重复数组 复制数组的模块
make sure there are no duplicate names in the result. •Find the IDs and names of all students who have not taken any course offering before Spring 2009. 11 •For each department, find the maximum ...
Kth Largest Element in an Array 桶排序 First Missing Positive 计数排序 H-Index 基数排序 Maximum Gap 其他 Largest Number 小结 查找 Search for a Range Search Insert Position Search in Rotated Sorted ...
Fast Duplicate File Finder is a powerful utility for finding duplicate files in a folder and all its sub folders. The duplicate remover has the following features: Find DUPLICATE files or find ...
(Duplicate Elimination) Use a one-dimensional array to solve the following problem: Write an app that inputs five numbers, each of which is between 10 and 100, inclusive. As each number is read, ...
Fast Duplicate File Finder
FirmTools Duplicate Photo Finder 相似图像查询软件 你电脑中如果有很多图像,有很多可能是一个logo只差,你用其他md5检测软件是不能快速找出来的。这个软件可以搜索相似的图像,你查看后选择删除,非常的方便。 ...
duplicate绝对干货。利用duplicate复制数据库,文档中包换每一步的试验步骤,详细说明了每一步的作用及用途,和注意事项,一步一步至试验成功,绝对一次成功。
Oracle RMAN DUPLICATE教程
Copy or duplicate an item Lock and unlock an item Edit a field in the Experience Editor Edit the website content Manage associated content Delete an item Edit the layout of an item Reset the ...
Rman通过duplicate创建standby
Duplicate File Finder单文件