Leetcode Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


整体思路是:整数的32个bits,出现次数mod 3后必余0, 1, 2

  int singleNumber(int A[], int n) {
      int n1=0, n2=0; // n1为mod 3余1的bits,n2为mod 3余2的bits
      for (int i=0; i<n; ++i) {
          int n0 = ~(n1|n2); // 若非余1也非余2,就是余0了
          // 若「原本就余2且bit为0」或「原本余1且bit为1」,则该bit更新后余2
          n2 = (n2&~A[i]) | (n1&A[i]);
          // 若「原本就余1且bit为0」或「原本余0且bit为1」,则该bit更新后余1
          n1 = (n1&~A[i]) | (n0&A[i]);
      return n1; // 余1的bits即为答案