​LeetCode刷題實戰137:只出現一次的數字 II

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做只出現一次的數字 II，我們先來看題面：https://leetcode-cn.com/problems/single-number-ii/

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

題意給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現了三次。找出那個只出現了一次的元素。你的算法應該具有線性時間複雜度。你可以不使用額外空間來實現嗎？

示例 1:

輸入: [2,2,3,2]
輸出: 3

示例 2:

輸入: [0,1,0,1,0,1,99]
輸出: 99

解題由於所有數都是整數，所以最大位數為32位，對於出現三次的數，統計每一位上1出現的次數一定能被3整除，而不能被三整除的位一定是單獨出現的數造成的，所以依次統計每一位的次數，並把不能被3整除的位數設為1賦給結果。C++代碼如下，非常簡單 。

class Solution {
public:
    int singleNumber(vector<int>& nums) {int res = 0;
        for(int i = 0; i < 32; i++){
            int sum = 0;
            for(int num: nums)
                if((num >> i) & 1)
                    sum++;
            if(sum % 3)
                res |= 1 << i;
        }
        return res;
    }
};

好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。