当前位置：首页 > news >正文

前k个高频元素

news 来源：原创 2025/6/19 5:34:51

pair<int int>：用于存储两个数字。（pair<int string>用于存储一个整数和一个字符串）

const pair<int int>：表示pair对象是常量，一旦初始化以后，其内部的两个成员值都不能被修改。

bool operator()：是C++ 中函数调用运算符重载，以下是其用法介绍：
基本概念

在C++ 里，一般对象使用 () 调用函数，而通过重载 operator() ，能让自定义类型的对象也像函数一样被调用，这种对象被称为函数对象或仿函数。
语法形式

class ClassName {
public:bool operator()(参数列表) {// 函数体逻辑// 通常返回一个bool值用于比较等操作return 比较结果; }
};
class Compare {
public:bool operator()(int a, int b) {return a > b; }
};

这里 Compare  类重载了 operator()  ，创建 Compare  类对象后，就能像函数一样调用它来比较两个整数大小。
在优先队列等场景的应用
优先队列：在定义优先队列时指定比较规则。如 priority_queue<int, vector<int>, Compare> pq;   ，这里 Compare  类中重载的 operator()  决定了优先队列内元素的比较方式和堆的类型（大顶堆或小顶堆）。像前面代码里 mycomparison  类中 bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs)  ，通过比较 lhs.second  和 rhs.second  来确定小顶堆的顺序。
算法中的谓词：在一些标准算法（如 sort  排序算法）中作为谓词（判断条件）。

sort(arr, arr + n, Compare());

可以利用重载的 operator() 实现自定义排序规则。
调用方式
创建仿函数对象后，就可像普通函数那样调用。例如：

Compare comp;
bool result = comp(5, 3); // 调用operator()，返回5 > 3的结果，即true

::iterator :在C++中， ::iterator 是一种嵌套类型（Nested Type），用于表示容器（如 vector 、 map 、 list 等）的迭代器类型。

::iterator 的含义：:: 是作用域解析运算符，表示 iterator 是其所属作用域（如类、命名空间）内定义的类型.

对于容器类（如 std::vector 、 std::unordered_map ）， iterator 是容器类内部嵌套定义的类型，用于指向容器中的元素。

vector<int>::iterator it; // 定义一个 vector<int> 的迭代器 it
map<std::string, int>::iterator mit; // 定义一个 map<string, int> 的迭代器 mit

2. 迭代器的分类
不同容器的 iterator  具有不同的特性（根据C++迭代器类型划分）：
- 输入迭代器：只能读取元素，单向移动（如 std::istream_iterator ）。
- 输出迭代器：只能写入元素，单向移动。
- 前向迭代器：支持单向移动和读写（如 std::forward_list  的 iterator ）。
- 双向迭代器：支持双向移动（ ++  和 -- ），如 std::list 、 std::set  的 iterator 。
- 随机访问迭代器：支持随机访问（如 it + n ），如 std::vector 、 std::deque  的 iterator 。
容器的 iterator  类型由其底层数据结构决定，例如：
vector  的 iterator  是随机访问迭代器。
unordered_map  的 iterator  是双向迭代器（不支持随机访问）。
3. 与其他嵌套类型的对比
容器中除了 iterator ，还有其他常见的嵌套类型：
const_iterator ：指向 const  元素的迭代器，不允许通过迭代器修改元素值。
vector<int>::const_iterator cit = vec.begin(); // cit 不能修改元素
reverse_iterator ：反向迭代器，用于逆序遍历容器（如 vec.rbegin() ）。
size_type ：表示容器大小的无符号整数类型（如 std::vector<int>::size_type ）。
4. 为什么需要 ::iterator ？
类型依赖：迭代器类型是容器类的内部实现细节，不同容器的迭代器类型不同（如 vector  和 list  的迭代器完全不同）。
作用域限定：通过 ::  明确指定 iterator  属于某个容器类的作用域，避免命名冲突。
示例：遍历 std::list<int>

int main() {std::list<int> myList = {1, 2, 3};    // 使用 ::iterator 遍历std::list<int>::iterator it;for (it = myList.begin(); it != myList.end(); ++it) {std::cout << *it << " "; // 输出：1 2 3（顺序确定，因为 list 是双向链表）}return 0;
}

5. 类型推导与 auto （C++11+）

C++11 引入的 auto 关键字可以自动推导迭代器类型，简化代码：

int main() {std::vector<int> myVec = {10, 20, 30};// 无需显式写出 ::iterator，auto 自动推导为 std::vector<int>::iteratorfor (auto it = myVec.begin(); it != myVec.end(); ++it) {std::cout << *it << " "; // 输出：10 20 30}return 0;
}

本质上， auto it = myVec.begin(); 中的 it 类型仍是vector<int>::iterator ，但 auto 省略了冗长的类型书写。

总结
::iterator 是容器类内部定义的嵌套类型，表示该容器的迭代器。
用于遍历容器元素，支持根据容器特性（如顺序、无序、链表、数组）进行相应的移动操作。
通过 auto 关键字可简化迭代器的定义，但理解其本质有助于深入掌握容器与迭代器的关系。

大顶堆和小顶堆

区别：

大顶堆：每个节点的值都大于或等于其左右子节点的值，堆顶元素是整个堆中的最大值。
小顶堆：每个节点的值都小于或等于其左右子节点的值，堆顶元素是整个堆中的最小值。

应用场景：

大顶堆：常用于获取一组数据中的前 k 个最大值，例如在一些任务调度算法中，可根据任务的优先级构建大顶堆，优先级高的任务先执行。
小顶堆：常用于获取一组数据中的前 k 个最小值，如在实时系统中，可根据事件的发生时间构建小顶堆，先处理最早发生的事件。

代码实现差异：

大顶堆：在比较父子节点大小时，通常是父节点的值大于等于子节点的值。例如在C++ 中，实现大顶堆的 push 操作时，会将新元素与父节点比较，如果新元素大于父节点，则交换位置。
小顶堆：比较父子节点大小时，父节点的值小于等于子节点的值。在实现 push 操作时，若新元素小于父节点，就交换位置。

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

class Solution {
public:class mycomparison{public:bool operator()(pair<int,int>&lhs,const pair<int,int>&rhs){return lhs.second>rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int>map;for(int i=0;i<nums.size();i++){map[nums[i]]++;}priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison>pri_que;for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){pri_que.push(*it);if(pri_que.size()>k){pri_que.pop();}}vector<int>result(k);for(int i=k-1;i>=0;i--){result[i]=pri_que.top().first;pri_que.pop();}return result;}};

大顶堆和小顶堆

区别：

应用场景：

代码实现差异：

相关文章：