力扣 137. 只出现一次的数字

比眉伴天荒 2023-07-13 12:29 18阅读 0赞

**题目描述**

给定一个 **非空 **整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

**说明**：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

**示例 1**:

输入: [2,2,3,2]
    输出: 3

**示例 2**:

输入: [0,1,0,1,0,1,99]
    输出: 99

**解决方案**

**综述**

该问题看起来很简单，使用 Set 或 HashMap 可以在 O(N) 的时间和 O(N) 的空间内解决。

真正的挑战在于 Google 面试官要求使用常数空间解决该问题（最近 6 个月该问题在 Google 上非常流行），测试应聘者是否熟练位操作。

![format_png][]

**方法一：HashSet**

将输入数组存储到 HashSet，然后使用 HashSet 中数字和的三倍与数组之和比较。

3 × (a + b + c) - ( a + a + a + b + b + b + c) = 2c

**Python 实现**

class Solution:
        def singleNumber(self, nums):
            return (3 * sum(set(nums)) - sum(nums)) // 2

**Java 实现**

class Solution {
      public int singleNumber(int[] nums) {
        Set<Long> set = new HashSet<>();
        long sumSet = 0, sumArray = 0;
        for(int n : nums) {
          sumArray += n;
          set.add((long)n);
        }
        for(Long s : set) sumSet += s;
        return (int)((3 * sumSet - sumArray) / 2);
      }
    }

**复杂度分析**

*  时间复杂度：O(N)，遍历输入数组。
 *  空间复杂度：O(N)，存储 N / 3 个元素的集合。

方法二：HashMap

遍历输入数组，统计每个数字出现的次数，最后返回出现次数为 1 的数字。

**Python 实现**

from collections import Counter
    class Solution:
        def singleNumber(self, nums):
            hashmap = Counter(nums)
                
            for k in hashmap.keys():
                if hashmap[k] == 1:
                    return k

**Java 实现**

class Solution {
      public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        for (int num : nums)
          hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);
    
        for (int k : hashmap.keySet())
          if (hashmap.get(k) == 1) return k;
        return -1;
      }
    }

**复杂度分析**

*  时间复杂度：O(N)，遍历输入数组。
 *  空间复杂度：O(N)，存储 N / 3 个元素的 Set。

方法三：位运算符：NOT，AND 和 XOR

**思路**

使用 **位运算符 **可以实现 O(1) 的空间复杂度。

![format_png 1][]

**XOR**

该运算符用于检测出现奇数次的位：1、3、5 等。

0 与任何数 XOR 结果为该数。

![format_png 2][]

两个相同的数 XOR 结果为 0。

![format_png 3][]

以此类推，只有某个位置的数字出现奇数次时，该位的掩码才不为 0。

![format_png 4][]

因此，可以检测出出现一次的位和出现三次的位，但是要注意区分这两种情况。

**AND 和 NOT**

为了区分出现一次的数字和出现三次的数字，使用两个位掩码：`seen_once` 和 `seen_twice`。

思路是：

*  仅当 `seen_twice` 未变时，改变 `seen_once`。
 *  仅当 `seen_once` 未变时，改变`seen_twice`。

![format_png 5][]

位掩码 `seen_once` 仅保留出现一次的数字，不保留出现三次的数字。

**Python 实现**

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            seen_once = seen_twice = 0
            
            for num in nums:
                # first appearance: 
                # add num to seen_once 
                # don't add to seen_twice because of presence in seen_once
                
                # second appearance: 
                # remove num from seen_once 
                # add num to seen_twice
                
                # third appearance: 
                # don't add to seen_once because of presence in seen_twice
                # remove num from seen_twice
                seen_once = ~seen_twice & (seen_once ^ num)
                seen_twice = ~seen_once & (seen_twice ^ num)
    
            return seen_once

**Java 实现:**

class Solution {
      public int singleNumber(int[] nums) {
        int seenOnce = 0, seenTwice = 0;
    
        for (int num : nums) {
          // first appearence: 
          // add num to seen_once 
          // don't add to seen_twice because of presence in seen_once
    
          // second appearance: 
          // remove num from seen_once 
          // add num to seen_twice
    
          // third appearance: 
          // don't add to seen_once because of presence in seen_twice
          // remove num from seen_twice
          seenOnce = ~seenTwice & (seenOnce ^ num);
          seenTwice = ~seenOnce & (seenTwice ^ num);
        }
    
        return seenOnce;
      }
    }

**复杂度分析**

*  时间复杂度：O(N)，遍历输入数组。
 *  空间复杂度：O(1)，不使用额外空间。

转载自：[https://mp.weixin.qq.com/s/gXm5nGY0RD7Y0iUyCRQLXg][https_mp.weixin.qq.com_s_gXm5nGY0RD7Y0iUyCRQLXg]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9RRDZ2UHVseHl5WE9sdVVxN3FCdG9vbmFReFpNdlIyaGFHZ3RUTmZhTXZVQlVIOWZDWlV2a3VzNDJLVUtQa2liMkQ2Q0ZCTW1QTWVpYmV5S2MzaWFjRWljdEEvNjQw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9RRDZ2UHVseHl5WE9sdVVxN3FCdG9vbmFReFpNdlIyaDJpYXNmalNNUHpnaWFFN0V4OWlhZU9TckNubGJFa1ZzWDZSME15M0t6MzU4U0ZQTnBlWXlnejBGdy82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9RRDZ2UHVseHl5WE9sdVVxN3FCdG9vbmFReFpNdlIyaDBIZHBZWWh2Vm1pYzNqRms3WjJyajJqcW50UkQ3Q0ZVR3dWQU9XVHA4amxsejBNSE11VlBad0EvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9RRDZ2UHVseHl5WE9sdVVxN3FCdG9vbmFReFpNdlIyaHFhaWJlUlhmQ1hWZlpYaGljQ28waE9veXNoSkFKRVA5RGlhaGM3Ym9HWlJRQVhLZjU4RUtlY0czUS82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9RRDZ2UHVseHl5WE9sdVVxN3FCdG9vbmFReFpNdlIyaDdyZ0tMd0pra0wyaWE1NkZwM25CaWJPRU9LenZ5TnlJa1VyWlFLMUZhbUZmdElBeEc4dW81cW9BLzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9RRDZ2UHVseHl5WE9sdVVxN3FCdG9vbmFReFpNdlIyaFZlaEZCaWJyd3hDU2VBaklxS2RXbFhFRmh5UW4zeXJNWDdLandYNHNOc0t4Y1ZqOWJ5MXdKSkEvNjQw?x-oss-process=image/format,png
[https_mp.weixin.qq.com_s_gXm5nGY0RD7Y0iUyCRQLXg]: https://mp.weixin.qq.com/s/gXm5nGY0RD7Y0iUyCRQLXg