算法训练 消失的数字 java

资源限制

时间限制：1.0s   内存限制：256.0MB

　　消失的数字

问题描述

　　有2*n个整数，已知每个数字出现了偶数次，现在一个数字消失了，请你编程找出这个数字。

输入格式

　　输入第一行包括一个正整数n，表示共2*n个整数。

　　第二行包括2*n-1个整数。

输出格式

　　共一行，只有一个整数，表示消失的那个数字。

样例输入

4

2 -1 2 3 -1 2 3

样例输出

2

数据规模和约定

　　n<=1000000

　　每个整数在int范围内

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Map arr = new HashMap<>();

		for (int i = 0; i < 2 * n - 1; i++) {
			int tmp = sc.nextInt();
			if (arr.isEmpty()) {
				arr.put(tmp, 1);
			} else {
				if (arr.containsKey(tmp)) {
					arr.put(tmp, arr.get(tmp) + 1);
				} else {
					arr.put(tmp, 1);
				}
			}
		}

		for (Integer i : arr.keySet()) {
			if (arr.get(i) % 2 != 0) {
				System.out.println(i);
				break;
			}
		}

	}

}

最后一个运行超时，欢迎大佬指正~