题目内容

给定一个长度为 $n$ 的整数数组 $nums$，其中恰好有两个元素只出现一次，其余所有元素都恰好出现两次。

请找出这两个只出现一次的元素。

两个元素可以按照任意顺序输出。

要求设计并实现时间复杂度为 $O(n)$，且仅使用 $O(1)$ 额外空间的算法。

输入描述

第一行输入一个整数 $n$，表示数组 $nums$ 的长度。

第二行输入 $n$ 个整数 $nums_i$，表示数组中的各个元素，相邻整数之间用空格分隔。

约束

$2 \le n \le 3 \times 10^4$

$-2^{31} \le nums_i \le 2^{31}-1$

数组中恰好有两个元素只出现一次。

除这两个元素外，其余所有元素都恰好出现两次。

要求算法的时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

输出描述

输出两个整数，表示数组中只出现一次的两个元素，相邻整数之间用空格分隔。

两个元素可以按照任意顺序输出。

样例1

输入

6
1 2 1 3 2 5

输出

3 5

说明

数组中元素 $1$ 和 $2$ 都出现了 $2$ 次。

元素 $3$ 和 $5$ 只出现了 $1$ 次，因此输出 $3$ 和 $5$。

输出 $5\ 3$ 同样正确。

样例2

输入

2
-1 0

输出

-1 0

说明

数组中只有两个元素 $-1$ 和 $0$，它们都只出现了 $1$ 次。

因此答案为 $-1$ 和 $0$。

样例3

输入

2
0 1

输出

1 0

说明

元素 $0$ 和 $1$ 都只出现了 $1$ 次，因此它们就是需要找出的两个元素。