137. Single Number II.md

137. Single Number II

---

leetcode Daily Chanlenge on June 22, 2020.

---

Given a non-empty 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?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

---

Solution

• mine
  • Java

    • count every bit value of 1, if count % 3 != 0, the res in this bit is 1.

      Runtime: 1 ms, faster than 78.38%,Memory Usage: 38.8 MB, less than 15.79% of Java online submissions

      //O(N)time O(1)space
      public int singleNumber(int[] nums) {
          int res = 0;
          for (int i = 0; i < 32; i++) {
              int t = 0;
              for (int num : nums) {
                  t += (num >> i) & 1;
              }
              if (t % 3 != 0) {
                  res |= 1 << i;
              }
          }
          return res;
      }
      

---

• the most votes

  • Karnaugh map,

    • detail explanation in leetcode
    • detail explanation in leetcode-cn

    Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.1 MB, less than 15.79% of Java online submissions

    //O(N)time  O(1)space
    public int singleNumber(int[] nums) {
        int seenOnce = 0, seenTwice = 0;
    
        for (int num : nums) {
            // first appearence:
            // add num to seen_once
            // don't add to seen_twice because of presence in seen_once
    
            // second appearance:
            // remove num from seen_once
            // add num to seen_twice
    
            // third appearance:
            // don't add to seen_once because of presence in seen_twice
            // remove num from seen_twice
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }
        return seenOnce;
    }
    

---