剑指 Offer 56 - II. 数组中数字出现的次数 II（位运算 / 哈希表 / 排序）-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指 Offer 56 - II. 数组中数字出现的次数 II（位运算 / 哈希表 / 排序）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

链接：剑指 Offer 56 - II. 数组中数字出现的次数 II
难度：中等

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

方法一：

位运算：

看不懂学不会，直接看力扣题解吧。

方法二：

哈希表：

人类的方法，没技术含量，统计出现次数。

代码二：

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

时间复杂度O(N)。
空间复杂度O(N)。

方法三：

排序：

排个序，看左右值是否相等，没相等的就是单独出现的数。

代码三：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int len = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i < len; i++)
        {
            if((i != 0 ? nums[i] != nums[i - 1] : true) && (i != len - 1 ? nums[i] != nums[i + 1] : true)) return nums[i];
        }
        return 0;
    }
};