侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-09-29 / 0 评论 / 0 点赞 / 15 阅读 / 718 字 / 正在检测是否收录...

题目


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

输入格式

第一行包含一个整数 NN,表示数组的长度。

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

输出格式

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

输入样例:

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;
            }
        }
    }
}

方法二:数学

思路

若数组的长度为 nn,那其中的数就是 1n11\sim n-1 ,把数组中的数加起来减去 x=1n1x\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);
    }
}

方法三:位运算

思路

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

具体来说:把 1n1 \sim n 全部异或在一起得到一个数,再把它与数组中的所有数字都做一次异或运算,此时 1n1 \sim n 中只出现一次的数字参与了两次异或运算被全部消除了,而出现两次的数字一共参与了三次异或运算,而我们知道 xxx=xx \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);
    }
}

0

评论区