2. 找出单独出现的数字

XMOJ 2. 找出单独出现的数字

题目：2. 找出单独出现的数字

描述:

给出N个数字。其中仅有一个数字出现过一次，其他数字均出现过两次，找出这个出现且只出现过一次的数字。要求时间和空间复杂度最小。

输入:

输入多个数字，每个数字以空格分开。数字数量 N < 20，输入数字的最大值小于 256.

输出:

输出内容为只出现过唯一一次的数字

输入样例:

10 10 11 12 12 11 16

输出样例:

16

方法：异或

思路：异或，a^b^b = a，将0与输入数据逐个异或即可得出答案。

运行数据：最大执行时间：85.34 ms，内存消耗：17340 KiB

复杂度分析：

• 时间复杂度：O(n)，n为输入数字个数。
• 空间复杂度：O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import java.util.Scanner;

public class Main {

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String line;
        line = scan.nextLine();
        short ans = 0;
        for (String string : line.split(" ")) {
            ans ^= Short.parseShort(string);
        }
        System.out.println(ans);
    }
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！