## 哈希表与排序组合：仿函数与Lambda表达式解题实践

在力扣算法实践中，哈希表与排序的组合应用是解决多类问题的有效策略。本文将通过具体问题，展示如何使用C++的仿函数和Lambda表达式两种方法，高效解决涉及元素统计、分组和排序的算法题目。

### 哈希表与排序的协同作用

哈希表提供O(1)时间复杂度的元素查找和插入，而排序能帮助组织数据的有序结构。结合两者可以解决需要同时考虑元素存在性和顺序的问题。

**基础应用场景分类：**

1. 频率统计与排序

2. 元素分组与聚合

3. 存在性检查与顺序处理

4. 去重与排序组合

### 方法一：使用仿函数（Functor）

仿函数是通过重载operator()的类对象，在排序等场景中提供灵活的比较逻辑。

**问题示例：按出现频率排序数组元素**

给定一个整数数组，按元素出现频率降序排序。如果频率相同，按值升序排序。

```cpp

#include <vector>

#include <unordered_map>

#include <algorithm>

#include <iostream>

using namespace std;

// 自定义仿函数用于排序

class FrequencyComparator {

private:

    unordered_map<int, int>& freqMap;

    

public:

    FrequencyComparator(unordered_map<int, int>& map) : freqMap(map) {}

    

    bool operator()(int a, int b) const {

        if (freqMap[a] != freqMap[b]) {

            return freqMap[a] > freqMap[b]; // 频率高的在前

        }

        return a < b; // 频率相同，值小的在前

    }

};

vector<int> frequencySortWithFunctor(vector<int>& nums) {

    // 步骤1：统计频率

    unordered_map<int, int> freq;

    for (int num : nums) {

        freq[num]++;

    }

    

    // 步骤2：使用仿函数排序

    vector<int> result = nums;

    sort(result.begin(), result.end(), FrequencyComparator(freq));

    

    return result;

}

```

**仿函数的优势：**

- 可以保存状态（如频率映射的引用）

- 代码结构清晰，可复用

- 性能与普通函数相当

**更复杂的仿函数示例：字符串分组**

```cpp

class AnagramGrouper {

public:

    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        unordered_map<string, vector<string>> groups;

        

        // 使用仿函数处理键生成

        struct KeyGenerator {

            string operator()(const string& str) {

                string key = str;

                sort(key.begin(), key.end());

                return key;

            }

        } keyGen;

        

        // 分组

        for (const string& str : strs) {

            string key = keyGen(str);

            groups[key].push_back(str);

        }

        

        // 提取结果

        vector<vector<string>> result;

        for (auto& pair : groups) {

            result.push_back(move(pair.second));

        }

        

        return result;

    }

};

```

### 方法二：使用Lambda表达式与捕获

Lambda表达式提供更简洁的语法，特别适合一次性使用的比较逻辑。

**相同问题的Lambda解法**

```cpp

vector<int> frequencySortWithLambda(vector<int>& nums) {

    // 统计频率

    unordered_map<int, int> freq;

    for (int num : nums) {

        freq[num]++;

    }

    

    // 使用Lambda表达式排序

    vector<int> result = nums;

    sort(result.begin(), result.end(), 

         [&freq](int a, int b) {

             if (freq[a] != freq[b]) {

                 return freq[a] > freq[b];

             }

             return a < b;

         });

    <"n6.adgp.cn"><"w3.adgp.cn"><"g7.adgp.cn">

    return result;

}

```

**Lambda表达式的捕获机制**

```cpp

void demonstrateLambdaCapture() {

    vector<int> nums = {1, 1, 2, 2, 2, 3};

    unordered_map<int, int> freq;

    

    // 值捕获示例

    auto valueCaptureExample = [freq]() mutable {

        // freq是副本，可以修改但不影响外部

        cout << "Value capture example" << endl;

    };

    

    // 引用捕获示例

    auto referenceCaptureExample = [&freq]() {

        // 直接操作外部freq

        for (int num : {1, 2, 3}) {

            freq[num] = num * 10;

        }

    };

    

    // 混合捕获

    int threshold = 2;

    auto mixedCapture = [&freq, threshold](int num) {

        return freq[num] > threshold;

    };

}

```

### 实战问题解析

**问题一：前K个高频元素**

找到数组中出现频率前k高的元素。

```cpp

// 使用Lambda表达式的解法

vector<int> topKFrequentLambda(vector<int>& nums, int k) {

    // 统计频率

    unordered_map<int, int> freq;

    for (int num : nums) {

        freq[num]++;

    }

    

    // 使用优先队列（最小堆）找出前k个

    auto compare = [&freq](int a, int b) {

        return freq[a] > freq[b]; // 最小堆，频率小的在顶部

    };

    

    priority_queue<int, vector<int>, decltype(compare)> minHeap(compare);

    

    for (auto& pair : freq) {

        minHeap.push(pair.first);

        if (minHeap.size() > k) {

            minHeap.pop(); // 移除频率最小的

        }

    }

    

    // 提取结果

    vector<int> result(k);

    for (int i = k - 1; i >= 0; i--) {

        result[i] = minHeap.top();

        minHeap.pop();

    }

    

    return result;

}

// 使用仿函数的解法

class TopKFrequentFunctor {

public:

    vector<int> topKFrequent(vector<int>& nums, int k) {

        unordered_map<int, int> freq;

        for (int num : nums) freq[num]++;

        

        // 定义比较仿函数

        struct Compare {

            unordered_map<int, int>& freq;

            Compare(unordered_map<int, int>& f) : freq(f) {}

            

            bool operator()(pair<int, int>& a, pair<int, int>& b) {

                return a.second > b.second; // 最小堆

            }

        };

        

        priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> 

            minHeap(Compare(freq));

        

        for (auto& p : freq) {

            minHeap.push(p);

            if (minHeap.size() > k) {

                minHeap.pop();

            }

        }

        

        vector<int> result;

        while (!minHeap.empty()) {

            result.push_back(minHeap.top().first);

            minHeap.pop();

        }

        

        return vector<int>(result.rbegin(), result.rend());

    }

};

```

**问题二：字母异位词分组优化**

```cpp

vector<vector<string>> groupAnagramsOptimized(vector<string>& strs) {

    // 使用自定义哈希函数

    auto arrayHash = [](const array<int, 26>& arr) -> size_t {

        size_t hash = 0;

        for (int count : arr) {

            hash = hash * 31 + count; // 简单哈希组合

        }

        return hash;

    };

    

    // 使用unordered_map的自定义哈希和比较

    unordered_map<array<int, 26>, vector<string>, 

                 decltype(arrayHash)> groups(0, arrayHash);

    

    for (const string& str : strs) {

        array<int, 26> count{};

        for (char c : str) {

            count[c - 'a']++;

        }

        groups[count].push_back(str);

    }

    

    vector<vector<string>> result;

    for (auto& pair : groups) {

        result.push_back(move(pair.second));

    }<"q9.adgp.cn"><"t2.adgp.cn"><"i5.adgp.cn">

    

    return result;

}

```

### 性能对比与选择建议

**时间复杂度分析**

```cpp

void performanceAnalysis() {

    vector<int> testData;

    for (int i = 0; i < 100000; i++) {

        testData.push_back(rand() % 100);

    }

    

    // 测试Lambda版本

    auto start = chrono::high_resolution_clock::now();

    auto result1 = frequencySortWithLambda(testData);

    auto end = chrono::high_resolution_clock::now();

    auto lambdaTime = chrono::duration_cast<chrono::microseconds>(end - start);

    

    // 测试仿函数版本

    start = chrono::high_resolution_clock::now();

    auto result2 = frequencySortWithFunctor(testData);

    end = chrono::high_resolution_clock::now();

    auto functorTime = chrono::duration_cast<chrono::microseconds>(end - start);

    

    cout << "Lambda版本耗时: " << lambdaTime.count() << "微秒" << endl;

    cout << "仿函数版本耗时: " << functorTime.count() << "微秒" << endl;

    

    // 验证结果一致性

    bool same = equal(result1.begin(), result1.end(), result2.begin());

    cout << "结果一致性: " << (same ? "是" : "否") << endl;

}

```

**选择策略建议**

1. **使用Lambda表达式当：**

   - 比较逻辑简单，一次性使用

   - 需要捕获局部变量

   - 代码简洁性优先

2. **使用仿函数当：**

   - 比较逻辑复杂，需要多个方法

   - 需要保存复杂状态

   - 代码需要复用

   - 调试时需要明确的函数名

### 高级技巧与模式

**模板化仿函数**

```cpp

template<typename T>

class GenericFrequencyComparator {

private:

    unordered_map<T, int>& freqMap;

    

public:

    GenericFrequencyComparator(unordered_map<T, int>& map) : freqMap(map) {}

    

    bool operator()(const T& a, const T& b) const {

        if (freqMap[a] != freqMap[b]) {

            return freqMap[a] > freqMap[b];

        }

        return a < b;

    }

};

// 使用示例

vector<string> sortStringsByFrequency(vector<string>& strs) {

    unordered_map<string, int> freq;

    for (const auto& str : strs) freq[str]++;

    

    vector<string> result = strs;

    sort(result.begin(), result.end(), 

         GenericFrequencyComparator<string>(freq));

    

    return result;

}

```

**Lambda表达式作为算法参数**

```cpp

template<typename Container, typename Transformer>

auto transformAndSort(const Container& data, Transformer transform) {

    vector<decltype(transform(*data.begin()))> transformed;

    

    // 应用转换

    for (const auto& item : data) {

        transformed.push_back(transform(item));

    }

    

    // 排序转换后的结果

    sort(transformed.begin(), transformed.end());

    

    return transformed;

}

// 使用示例

void demonstrateTransform() {

    vector<int> numbers = {5, 2, 8, 1, 9};

    

    // 使用Lambda作为转换函数

    auto squaredAndSorted = transformAndSort(numbers, 

        [](int x) { return x * x; });

    

    for (int val : squaredAndSorted) {

        cout << val << " ";

    }

    cout << endl;

}

```

### 常见问题与调试技巧

**问题：Lambda捕获导致的问题**

```cpp

void commonLambdaIssues() {

    vector<int> data = {1, 2, 3, 4, 5};

    

    // 错误示例：捕获引用但对象已销毁

    auto createProblematicLambda = [&data]() {

        // 如果data在外部被销毁，这里会出错

        return data.size();

    };

    

    // 正确做法：根据需要选择捕获方式

    auto safeLambda1 = [data]() { return data.size(); }; // 值捕获

    auto safeLambda2 = [data = data]() { return data.size(); }; // C++14初始化捕获

}

```

**调试技巧**

```cpp

class DebuggableFunctor {

private:

    unordered_map<int, int>& freq;

    mutable int comparisonCount = 0; // 调试计数器

    

public:

    DebuggableFunctor(unordered_map<int, int>& f) : freq(f) {}

    

    bool operator()(int a, int b) const {

        comparisonCount++;

        cout << "比较 #" << comparisonCount 

             << ": " << a << "(" << freq[a] 

             << ") vs " << b << "(" << freq[b] << ")" << endl;

        

        if (freq[a] != freq[b]) {

            return freq[a] > freq[b];

        }

        return a < b;

    }

    

    int getComparisonCount() const { return comparisonCount; }

};

```

### 总结与最佳实践

哈希表与排序的组合应用是解决力扣中许多问题的有效模式。通过仿函数和Lambda表达式两种方法，我们可以：

1. **灵活处理复杂比较逻辑**：无论是基于频率、分组还是其他自定义规则

2. **保持代码清晰性**：Lambda适合简单逻辑，仿函数适合复杂场景

3. **实现高效算法**：两种方法在性能上表现相当，选择取决于具体需求

4. **提升代码可维护性**：合理的选择使代码更易理解和调试

在实际应用中，建议：

- 对于简单、一次性的比较，优先使用Lambda表达式

- 对于复杂、需要复用的比较逻辑，使用仿函数

- 注意捕获机制的选择，避免生命周期问题

- 在性能关键处进行测试，确保选择的方法满足要求

掌握这两种技术，能够更优雅地解决涉及哈希表和排序的各类算法问题，提升解题效率代码质量。在力扣刷题和实际工程中，这种组合策略都是值得掌握的实用技能。