leetcode：137. 只出现一次的数字 II

题目

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例：

  1. 输入：nums = [2,2,3,2]
  2. 输出：3
  1. 输入：nums = [0,1,0,1,0,1,99]
  2. 输出：99

解答 & 代码

依次求每个二进制位的和：假设求第 i 个二进制位

  • 如果整个数组所有元素第 i 个二进制位的和为 3 的倍数，那么只出现一次的元素的第 i 个二进制位为 0（因为其余每个元素的二进制位要么是 0，要么是 1，都重复出现 3 次，因此肯定是 3 的倍数）

  • 如果整个数组所有元素第 i 个二进制位的和除 3 余 1，那么只出现一次的元素的第 i 个二进制位为 1

    1. class Solution {
    2. public:
    3.   int singleNumber(vector<int>& nums) {
    4.       int result = 0;
    5.       // 遍历每个二进制位，对数组中所有元素的该位求和
    6.       for(int i = 0; i < 32; ++i)
    7.       {
    8.           int sum = 0;    // 第 i 位的和
    9.           for(int j = 0; j < nums.size(); ++j)    // 遍历数组中的所有元素
    10.           {
    11.               int bitVal = (nums[j] >> i) & 1;    // 第 j 个数的第 i 个二进制位
    12.               sum += bitVal;
    13.           }
    14.           // 若该位的和除 3 余 1，则只出现一次的元素的该位为 1
    15.           if(sum % 3 == 1)
    16.               result |= (1 << i);                    // 将答案的第 i 位置 1
    17.       }
    18.       return result;
    19.   }
    20. };

    复杂度分析：设数组包含 n 个数

  • 时间复杂度 O(n)：外循环遍历 32 位二进制位，来对每一位求和，时间复杂度 = O(32) = O(1)；内循环求该二进制位各个数的和，遍历数组中的每个数，时间复杂度 O(n)

  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 60.56% 的用户
  4. 内存消耗：9.2 MB, 在所有 C++ 提交中击败了 77.11% 的用户