题目链接

题意

数组中除了一个数出现过一次，其余数都出现了三次。找出这个数。

题解

这里用最简单的基于统计的方法。即出现过三次的数，其统计结果的每个位置上的数对3取余则为要找那个数相应位置的二进制值。
剑指offer 56 - II. 数组中数字出现次数II - 图1

代码

  1. class Solution {
  2. public:
  3.     int singleNumber(vector<int>& nums) {
  4.         //建立一个长度为32的数组，以便能存下数据范围内的每个数的二进制位情况
  5.         vector<int> bits(32, 0);
  6.         int i;
  7.         //首先对所有数字的每一位二进制进行统计
  8.         for (int n : nums) {
  9.             i = 0;
  10.             while (n) {
  11.                 bits[i++] += n & 1;
  12.                 n >>= 1;
  13.             }
  14.         }
  15.         //对每一个位置进行对3取余，得到的结果就是要找的数的二进制表示，再转换成数字就行了
  16.         int res = 0;
  17.         //从高位开始，这样才能逐渐把高位的值移动到对应的位置
  18.         for (int i = 31; i >= 0; i--) {
  19.             res <<= 1;
  20.             res += bits[i] % 3;
  21.         }
  22.         return res;
  23.     }
  24. };