题目描述(简单难度)

所有数字都是成对出现的,只有一个数字是落单的,找出这个落单的数字。

解法一

题目要求线性复杂度内实现,并且要求没有额外空间。首先我们考虑假如没有空间复杂度的限制。

这其实就只需要统计每个数字出现的次数,很容易想到去用 HashMap

遍历一次数组,第一次遇到就将对应的 key 置为 1。第二次遇到就拿到 key 对应的 value 然后进行加 1 再存入。最后只需要寻找 value1key 就可以了。

利用 HashMap 统计字符个数已经用过很多次了,比如 30 题49 题 等等,最重要的好处就是可以在 O(1) 下取得之前的元素,从而使得题目的时间复杂度达到 O(n)

当然,注意到这个题目每个数字出现的次数要么是 1 次,要么是 2 次,所以我们也可以用一个 HashSet ,在第一次遇到就加到 Set 中,第二次遇到就把当前元素从 Set 中移除。这样遍历一遍后,Set 中剩下的元素就是我们要找的那个落单的元素了。

public int singleNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        if (!set.contains(nums[i])) {
            set.add(nums[i]);
        } else {
            set.remove(nums[i]);
        }
    }
    return set.iterator().next();
}

当然,上边的解法空间复杂度是 O(n),怎么用 O(1) 的空间复杂度解决上边的问题呢?

想了很久,双指针,利用已确定元素的空间,等等的思想都考虑了,始终想不到解法,然后看了官方的 Solution ,下边分享一下。

解法二 数学推导

假设我们的数字是 a b a b c c d

怎么求出 d 呢?

只需要把出现过的数字加起来乘以 2 ,然后减去之前的数字和就可以了。

什么意思呢?

上边的例子出现过的数字就是 a b c d ,加起来乘以二就是 2 * ( a + b + c + d),之前的数字和就是 a + b + a + b + c + c + d

2 * ( a + b + c + d) - (a + b + a + b + c + c + d),然后结果是不是就是 d 了。。。。。。

看完这个解法我只能说 tql。。。

找出现过什么数字,我们只需要一个 Set 去重就可以了。

public int singleNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    int sum = 0;//之前的数字和
    for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
        sum += nums[i];
    }
    int sumMul = 0;//出现过的数字和
    for (int n : set) {
        sumMul += n;
    }
    sumMul = sumMul * 2;
    return sumMul - sum;
}

但上边的解法还是需要 O(n) 的空间复杂度,下边的解法让我彻底跪了。

解法三 异或

还记得位操作中的异或吗?计算规则如下。

0 ⊕ 0 = 0

1 ⊕ 1 = 0

0 ⊕ 1 = 1

1 ⊕ 0 = 1

总结起来就是相同为零,不同为一。

根据上边的规则,可以推导出一些性质

  • 0 ⊕ a = a
  • a ⊕ a = 0

此外异或满足交换律以及结合律。

所以对于之前的例子 a b a b c c d ,如果我们把给定的数字相互异或会发生什么呢?

  a ⊕ b ⊕ a ⊕ b ⊕ c ⊕ c ⊕ d
= ( a ⊕ a ) ⊕ ( b ⊕ b ) ⊕ ( c ⊕ c ) ⊕ d
= 000 ⊕ d
= d

是的,答案就这样出来了,我妈妈问我为什么要跪着。。。

java 里的异或是 ^ 操作符,初始值可以给一个 0

public int singleNumber(int[] nums) {
    int ans = 0;
    for (int i = 0; i < nums.length; i++) {
        ans ^= nums[i];
    }
    return ans;
}

解法一利用 HashMap 计数算是一个很常用的思想了。解法二的数学推导理论上还能想到,解法三的异或操作真的是太神仙操作了,自愧不如。

results matching ""

    No results matching ""