【位运算, 数学, 哈希表】唯一成对的数

题目

---

把 $1\sim n$ 这 $n$ 个数放到一个长度为 $n+1$ 的整数数组中，其中只有一个数出现了两次，找出这个数。

输入格式

第一行包含一个整数 $N$，表示数组的长度。

接下来一行给出 $N$ 个用空格分隔的整数表示数组中的元素。

输出格式

输出出现了两次的那个数。

输入样例：

5
1 2 3 4 3

输出样例：

3

解题

方法一：哈希表

思路

使用哈希表给数组中每个数计数，返回出现了两次的数。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            nums[i] = (int) in.nval;
        }
        // 输入完成
        int[] cnts = new int[n];
        for (int num : nums) {
            if (++cnts[num] == 2) {
                System.out.println(num);
                return;
            }
        }
    }
}

方法二：数学

思路

若数组的长度为 $n$，那其中的数就是 $1\sim n-1$ ，把数组中的数加起来减去 $\sum_{x=1}^{n-1}x$ 即是出现两次的数。

使用这种方法需要注意数字太多时可能会溢出。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            nums[i] = (int) in.nval;
        }
        // 输入完成
        int sum = 0;
        for (int num : nums) sum += num;
        int tmp = (n - 1) * n / 2;
        System.out.println(sum - tmp);
    }
}

方法三：位运算

思路

由异或运算的性质：对于任何数 $x$，都有 $x \oplus x = 0$，$x \oplus 0 = 0$，那么我们只需要利用这一条把出现一次的数字全部消除即可。

具体来说：把 $1 \sim n$ 全部异或在一起得到一个数，再把它与数组中的所有数字都做一次异或运算，此时 $1 \sim n$ 中只出现一次的数字参与了两次异或运算被全部消除了，而出现两次的数字一共参与了三次异或运算，而我们知道 $x \oplus x \oplus x = x$，于是该数字就被保留了下来。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            nums[i] = (int) in.nval;
        }
        // 输入完成
        int ans = 0;
        for (int i = 1; i < n; ++i) ans ^= i;
        for (int num : nums) ans ^= num;
        System.out.println(ans);
    }
}