Quick link to leetcode

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入： nums = [100,4,200,1,3,2]输出： 4 解释： 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入： nums = [0,3,7,2,5,8,4,6,0,1]输出： 9

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

实现

class Solution {
public:
    // 静态哈希函数，用于计算每个字母频次数组的哈希值
    static size_t arrayHash(const array<int, 26>& arr) {
        size_t hashValue = 0;
        hash<int> fn;

        for (const auto& i : arr) {
            hashValue = (hashValue << 1) ^ fn(i); // 随机哈希
        }
        return hashValue;
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 使用 unordered_map 来存储以字母频率为键的异位词分组
        unordered_map<array<int, 26>, vector<string>, decltype(&Solution::arrayHash)> dict(1000, &Solution::arrayHash);

        for (auto& s : strs) {
            array<int, 26> counts{};  // 初始化一个大小为 26 的数组来记录字母频率
            for (auto& c : s) {
                counts[c - 'a']++;  // 统计字母频率
            }
            dict[counts].emplace_back(s);  // 将当前单词添加到对应频率数组的分组
        }

        vector<vector<string>> ans;
        for (auto& entry : dict) {
            ans.push_back(move(entry.second));  // 将每个异位词分组添加到结果中
        }

        return ans;
    }
};