Duplicate Pair问题

Duplicate Pair

An array of length n, with address from 1 to n inclusive, contains entries from the set {1,2,...,n-1} and there's exactly two elements with the same value. Your task is to find out the value.

Input

Input contains several cases.
Each case includes a number n (1<n<=10^6), which is followed by n integers.
The input is ended up with the end of file.

Output

Your must output the value for each case, one per line.

Sample Input

2
1 1
4
1 2 3 2

Sample Output
1
2

 

import java.io.*;

public class DuplicatePair {
	public static void main(String[] args){
		File file = new File("D:\\arithmetic\\src\\duplicatePair.txt");
		if(!file.exists()){
			System.out.println("file is not exist!");
			return;
		}
		FileReader fileReader = null;
		BufferedReader reader = null;
		try {
			fileReader = new FileReader(file);
			reader = new BufferedReader(fileReader);
			int n = Integer.valueOf(reader.readLine());
			while(n != -1){
				int[] arr = new int[n/8+1];
				for(int i=0;i<n/8+1;i++)
					arr[i] = 0;
				String str = reader.readLine();
				String[] nums = str.split(" ");
				for(int i=0;i<nums.length;i++){
					int temp = Integer.valueOf(nums[i]);
					if(((1<<temp) & arr[temp/8]) == 0){
						arr[temp/8] |= 1<<temp;
					}else{
						System.out.println(temp);
					}
				}
				String strs = reader.readLine();
				if(strs != null){
					n = Integer.valueOf(strs);
				}else{
					n = -1;
				}
			}
			reader.close();
			fileReader.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

 

算法分析：

      看到这个题目也许你觉得很简单，只要根据n的大小创建一个数组，然后扫描各个整数，将该数对应的数组置为1。可是题目里的n是10^6级别，即使这样的开销也不小。

      最好的办法就是用每一个二进制位标记一个数字。每读取一个数的时候都先检查下对应的二进制是否为1，如果是就输出当前数。否则将对应的位置1，继续读取下一个数字。

评论

2 楼 celebration 2009-01-10  

knzeus 写道

为什么不直接加起来得到sum，再用sum减去n*(n-1)/2呢。

恩，是个很不错的方法。可是对于10^6这个级别的数进行加法，需要用数组来保存结果，因为最后的和是10^12级别。不过实现上也不是很复杂，谢谢提醒。

1 楼 knzeus 2008-11-12  

为什么不直接加起来得到sum，再用sum减去n*(n-1)/2呢。