【LeetCode】 137. Single Number II

Description

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?

給一個整數的非空陣列，每個元素出現三次，只有一個出現一次，請找到這個孤單的傢伙。

注意：你的演算法應該是線性複雜度(O(N))，你可以完成並不使用額外的空間嗎？

Example:

Example 1:

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


Example 2:

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

Solution

• 目前還沒想到比較好的解法，直接用map做hash table，存好之後找只出現一次的元素。

Code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> hash;
        for(int i=0;i<nums.size();i++)
        {
            hash[nums[i]]++;
        }
        for(auto i=hash.begin();i!=hash.end();i++)
            if(i->second==1)return i->first;
        return 0;
    }
};

tags: LeetCode C++