代码结构

class Solution {
public:
    int singleNumber(int* A, int n) {
        int bitCount[32] = {0}; // 统计每一位的1的个数

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 32; ++j) {
                bitCount[j] += (A[i] >> j) & 1; // 更新每一位的计数
            }
        }

        int result = 0;
        for (int j = 0; j < 32; ++j) {
            result |= (bitCount[j] % 3) << j; // 只取模3的结果
        }

        return result;
    }
};

详细步骤解析

  1. bitCount数组的初始化：这个数组用来记录每一位上1的出现次数。我们使用32个元素来处理32位整数。
  2. 外层循环：遍历输入数组A中的每一个元素。这里的n是数组的长度。
  3. 内层循环：对于每一个元素，我们需要检查它的每一位（从第0位到第31位）。
  4. 统计每一位的1的个数：A[i] >> j：将当前元素A[i]右移j位，这样我们可以检查当前位。& 1：与1进行位与运算，提取出最低位。如果当前位是1，结果将为1；如果是0，结果为0。bitCount[j] += ...：将当前位的统计结果加到bitCount[j]中。
  5. 构建结果：初始化result为0，用于存储只出现一次的元素。再次遍历bitCount数组，对于每一位： bitCount[j] % 3：由于其他数字出现了三次，所以在每一位上只出现一次的元素的1会在bitCount中留下非零值。<< j：将这个结果左移j位，以放置在正确的位置。result |= ...：使用按位或运算将结果累加到result中。
  6. 返回结果：最后返回构建出的只出现一次的元素。

复杂度分析

  • 时间复杂度：O(n)，其中n是数组的长度。我们只需要一次遍历数组和32次位操作。
  • 空间复杂度：O(1)。虽然使用了bitCount数组，但它的大小是固定的（32），不随输入规模而变化，因此认为是常量空间。

示例解释

假设输入数组为A = [2, 2, 3, 2]：

  • 统计过程： 对于2，二进制为0000 0010，统计后bitCount会变为[0, 1, 0, ..., 0]（第1位为1，其他为0）。对于3，二进制为0000 0011，统计后bitCount会变为[0, 2, 0, ..., 0]（第1和第2位为1，其他为0）。
  • 最终，bitCount为[0, 3, 0, ..., 0]，因为第1位的1出现了三次，result最终会只留下3。

总结

该方法高效利用位运算统计每一位的出现次数，并通过模运算找出只出现一次的元素，避免了使用额外的数据结构，从而节省空间。