【算法】数字只出现一次或两次

发表于 阅读次数：

判断数组中的所有的数字是否只出现一次。

给定一个数组 array，判断数组 array 中是否所有的数字只出现一次。
例如，arr = {1, 2, 3}，输出 YES。
又如，arr = {1, 2, 1}，输出 NO。
约束时间复杂度为 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Main {
    public static void main(String[] args) {
        final int[] data1 = {1, 2, 3};
        final int[] data2 = {1, 2, 1};

        System.out.println(getOnlyOnceStatus1(data1));
        System.out.println(getOnlyOnceStatus1(data2));
    }

    /**
     * 通过set来存储，比较数量
     *
     * @param data 数组
     * @return 结果
     */
    private static String getOnlyOnceStatus1(int[] data) {

        Set<Integer> result = new HashSet<>(data.length);
        for (int datum : data) {
            if (!result.add(datum)) {
                return "NO";
            }
        }

        if (result.size() == data.length) {
            return "YES";
        }
        return "NO";
    }
}
/*
YES
NO
*/

找出数组中只出现一次的数字，其它数字都出现了两次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Main {
    public static void main(String[] args) {
        final int[] data1 = {1, 2, 3, 3, 2, 1, 4, 6, 4};
        final int[] data2 = {1, 2, 1};

        System.out.println(xorIntArray(data1));
        System.out.println(xorIntArray(data2));
    }

    /**
     * 异或操作
     *
     * @param data 数组
     * @return 结果
     */
    private static Integer xorIntArray(int[] data) {

        if (data == null || data.length == 0) {
            return null;
        }
        if (data.length == 1) {
            return data[0];
        }
        int result = data[0];
        for (int i = 1; i < data.length; i++) {
            result ^= data[i];
        }

        return result;
    }
}
/*
6
2
*/