LeetCode 260. Single Number III [Medium]

发表于 更新于 分类于 ， 阅读次数：

LeetCode 260. Single Number III

题目来源：https://leetcode.com/problems/single-number-iii

题目难度：Medium

解答1[Java]：

核心思想

假设两个只出现一次的数为 a 和 b，先把所有的数做异或，这样的得到的结果为 a^b，如果 a^b 的二进制形式的某一位是 1，说明 a 和 b 两个数在这一位上不同，可以根据这一位把所有的数分为两个组，一组是这一位为 1 的，一组是这一位为 0。如果两个数相同，那么这样两个数肯定会分到同一组。但是 a 和 b 会被分到不同的组。这样，对任意一组的全部数字执行异或操作，那么就会得到 a 和 b 其中的一个。再用其中的一个和 a^b 做异或运算就可以得到另外一个数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] singleNumber(int[] nums) {
        int aXORb = 0;
        for (int i : nums) {
            aXORb ^= i;
        }
        // the last bit that a diffs b
        int mask = (aXORb & (aXORb - 1)) ^ aXORb;

        int a = 0;
        for (int i : nums) {
            if ((i & mask) != 0) {
                a = a ^ i;
            }
        }
        return new int[]{a, a ^ aXORb};
    }
}

解答2[Java]：

核心思想

使用 HashMap 计数。

代码

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
import java.util.*;

class Solution {
    public int[] singleNumber(int[] nums) {
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        List<Integer> result = new ArrayList<>();
        for (int num : nums) {
            if (map.get(num) == null) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }

        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();

        for (Map.Entry<Integer, Integer> entry : entries) {
            if (entry.getValue() == 1) {
                result.add(entry.getKey());
            }
        }

        int[] ret = new int[result.size()];
        Iterator<Integer> iter = result.iterator();
        for (int i = 0; i < ret.length; ++i) {
            ret[i] = iter.next();
        }

        return ret;
    }
}

解答3[Java]：

核心思想

对一个数，如果不在 set 中，就放进去，如果已经在 set 中，说明是成对的，就把原来的也移出去，最后剩下的就是不同的两个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.HashSet;

class Solution {
    public int[] singleNumber(int[] nums) {
        HashSet<Integer> ans = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (!ans.contains(nums[i])) {
                ans.add(nums[i]);
            } else {
                ans.remove(nums[i]);
            }
        }
        int[] result = new int[ans.size()];
        int i = 0;
        for (int num : ans) {
            result[i] = num;
            i++;
        }
        return result;
    }
}

补充

异或的基本运算：n^0 = n。