【MEDIUM】Single Number II

发布于: 2019-04-02 23:56
阅读: 31
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/single-number-ii/

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?

分析过程

  • 输入:一个整数数组,所有数字都出现了三次,只有一个数字出现了一次。
  • 输出:找到这个只出现了一次的数。
  • 思路:任何出现了三次的数字,每一位加起来不是 0 就是 3,和 3 取模都是 0。某个数字只出现了一次,那么就会出现某一位和 3 取模余 1,这个 1 就是只出现了一次的数字的。对 3 取模的过程可以写成位运算,见注释。

解决方法

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 00 + 1 = 01
        // 01 + 1 = 10
        // 10 + 1 = 00 相当于对 3 取模
        // 写成位运算的形式如下
        int a = 0, b = 0;
        for (int num : nums) {
            b = (b ^ num) & ~a;
            a = (a ^ num) & ~b;
        }
        return b;
    }
};

Thanks for reading.

All the best wishes for you! 💕