LeetCode题解–137. Single Number II

链接

LeetCode题目：https://leetcode.com/problems/single-number-ii/

难度：Medium

题目

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 题目大意是一个数组中只有一个数字出现一次，其余的数字都出现了三次，在线性时间内找出那个单独的数字。

分析

最简单的想法是用map，遍历一次数组将出现三次的数字删掉，最后剩下的数字就是所求的，但是空间复杂度是O(n)。 更好的做法是用一个长度为32的bits数组统计每个数字每一位中1出现的次数，线性扫描一遍数组后，对bits数组的每一位进行模3，这样就能知道单独的数字每一位是0或1，时间复杂度和用map的做法都是O(n)，因为bit数组大小固定所以空间复杂度降低到了O(1)。

代码

class Solution { public: int singleNumber(vector<int> &nums) { int bits[32] = {0}; for (auto num:nums) { for (int i = 0; i < 32; i++) { bits[i] += (num >> i) & 1; } } int ans = 0; for (int i = 0; i < 32; i++) { bits[i] %= 3; ans += bits[i] << i; } return ans; } };