Pair基础

在C++中，pair 是一个常用的模板类，用来将两个值组合成一个值对。它在处理关联数据时非常有用，例如在标准库中的map和set中常用到。以下是一些pair的常见操作和用法：

定义和初始化

1. 创建一个pair并初始化：

1
2
3
4
5
6
7
8
#include <iostream>
#include <utility> // for std::pair

int main() {
    std::pair<int, std::string> myPair(1, "Hello");
    std::cout << "First: " << myPair.first << ", Second: " << myPair.second << std::endl;
    return 0;
}

2. 使用std::make_pair函数创建一个pair：

1
2
3
4
5
6
7
8
#include <iostream>
#include <utility>

int main() {
    auto myPair = std::make_pair(1, "Hello");
    std::cout << "First: " << myPair.first << ", Second: " << myPair.second << std::endl;
    return 0;
}

访问元素

pair中的元素可以通过first和second成员来访问：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <utility>

int main() {
    std::pair<int, std::string> myPair(1, "Hello");

    // 访问元素
    std::cout << "First: " << myPair.first << ", Second: " << myPair.second << std::endl;

    // 修改元素
    myPair.first = 2;
    myPair.second = "World";

    std::cout << "First: " << myPair.first << ", Second: " << myPair.second << std::endl;

    return 0;
}

比较操作

pair 支持比较操作，包括相等、不等、小于、小于等于、大于和大于等于。比较操作按字典序进行，**即先比较first，如果first相等，再比较second**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <utility>

int main() {
    std::pair<int, std::string> pair1(1, "Hello");
    std::pair<int, std::string> pair2(2, "World");
    std::pair<int, std::string> pair3(1, "Hello");

    // 比较操作
    std::cout << (pair1 == pair2) << std::endl; // 输出 0 (false)
    std::cout << (pair1 != pair2) << std::endl; // 输出 1 (true)
    std::cout << (pair1 < pair2) << std::endl;  // 输出 1 (true)
    std::cout << (pair1 <= pair3) << std::endl; // 输出 1 (true)
    std::cout << (pair2 > pair1) << std::endl;  // 输出 1 (true)
    std::cout << (pair2 >= pair3) << std::endl; // 输出 1 (true)

    return 0;
}

使用在标准库容器中

pair 经常在标准库容器中使用，例如map和set。

1. 在map中使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> myMap;

    // 插入元素
    myMap.insert(std::make_pair(1, "One"));
    myMap.insert(std::make_pair(2, "Two"));

    // 访问元素
    for (const auto& elem : myMap) {
        std::cout << elem.first << ": " << elem.second << std::endl;
    }

    return 0;
}

2. 在set中使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set>
#include <utility>

int main() {
    std::set<std::pair<int, std::string>> mySet;

    // 插入元素
    mySet.insert(std::make_pair(1, "One"));
    mySet.insert(std::make_pair(2, "Two"));

    // 访问元素
    for (const auto& elem : mySet) {
        std::cout << elem.first << ": " << elem.second << std::endl;
    }

    return 0;
}

使用const auto& 来列举时，每个元素是const pair<>类型。

优先队列基础

priority_queue基础

CPP优先队列定义如下（需要#include<queue>)

priority_queue<Type, Container, Functional>

Container是存放元素的容器，默认用vector, Functional指出优先级的比较标准。

CPP的优先队列默认是大顶堆，Functional默认为less，即：

1
2
3
//对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;

如果想构造小顶堆，只需将Functional变为greater即可：

1
priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆

为什么默认为less就是大顶堆了呢？

默认情况下，std::priority_queue使用std::less作为比较函数，这相当于比较运算符<。这意味着，对于两个元素lhs和rhs (假设为bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs)：

​ • 如果lhs < rhs返回true，则priority_queue认为rhs的优先级高于lhs。

也就是说，priority_queue默认认为返回true表示lhs应该在rhs之下，因此将较大的元素放在堆顶。

自定义比较函数

这个Functional是可以自定义的，如果我们想把pair中second较小的放在堆顶，我们可以自定义比较函数如下：

1
2
3
bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
    return lhs.second > rhs.second;
}

如此一来，当rhs.second小于lhs.second时，该函数返回true，rhs优先级比lhs高。

题目描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

示例 2:

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

提示：

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 , n 是数组的大小。
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
  • 你可以按任意顺序返回答案。

思路解析

这题总的思想分为两部分： 统计频率，输出前k高元素。

统计频率

这题一开始我想的是空间换时间，即把nums数组中的元素看成下标，然后遍历数组，统计频率。这种方法只需要一个数组结构即可，但是由于我nums数组范围可以很大，导致可能会很浪费空间，于是改用map的方式统计频率。

map的方式也很简单明了。用哈希表的形式完成映射即可。

1
2
3
4
unordered_map<int,int> um; 
for (int n:nums){
    um[n] ++;
}

输出前k高元素

现在我们的任务是，如何选出map中前k高的值（只根据值不根据键来选），然后输出对应的键，我们希望这个过程的时间复杂度仅仅是n(这里的n代表map中的元素个数。

在这里我们抽象一下问题，不把它当作map来看，如果我们有一个int数组，我们想输出前k大的元素，如何在n的时间复杂度内完成这个任务呢？

如果用暴力算法，很显然需要kn的时间复杂度，从简单的情况出发，如果我们需要输出前2大的元素，我们只需要双指针即可，可双指针的方法也需要kn的时间复杂度。所以我们需要用空间换时间，考虑用一个数据结构来存储已经遍历过的有可能是最后解的结果，所以堆就成了这个数据结构的最佳选择。

我们构造一个大顶堆，将所有元素都插入到堆中，然后进行k次pop操作即可。但是除此之外，有一种更高效的方法，那就是构造一个k个元素的小顶堆，我们只需要将堆顶元素设置为第k大的元素即可，换句话说，只要将遍历到的比当前堆顶元素大的值插入到当前堆中，然后pop掉原来堆顶的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (const auto& p: um){
      if (minHeap.size() < k){  // 先将minHeap的值填到k
          minHeap.push(p);
      }
      else{
          if (minHeap.top().second < p.second){  // 如果遍历元素比当前堆顶元素大，那么就置换它们
              minHeap.pop();
              minHeap.push(p);
          }
      }
  }
  while (!minHeap.empty()){  // 最后输出minHeap中的first元素即可
      ans.push_back(minHeap.top().first);
      minHeap.pop();
  }

这里minHeap的优先级不是pair的默认先比较键再比较值，而是基于值的最小堆，所以我们需要自定义函数来定义优先级。

1
2
3
4
5
6
class myComparison{
public: 
    bool operator()(const pair<int,int>& p1, const pair<int,int>& p2){
        return p1.second > p2.second;
    }
};

然后在主函数中如下声明：

1
priority_queue<pair<int,int>, vector<pair<int,int>>, myComparison> minHeap;

本题思路不难，但是需要对CPP的STL容器进行融合使用，对练习STL容器来说是一道很好的习题。

类似习题

合并K个排序链表

​ • 题目链接： LeetCode 23. Merge k Sorted Lists

​ • 思路： 使用小顶堆将所有链表的头节点加入堆中，然后每次取出堆顶元素，将其后续节点再加入堆中，直到所有节点都被处理完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    class nodeComparison{
    public:
        bool operator()(const ListNode* n1, const ListNode* n2){
            return n1->val > n2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans = new ListNode(0);
        ListNode* p = ans;
        priority_queue<ListNode*, vector<ListNode*>, nodeComparison> minHeap;

        for (int i = 0; i < lists.size(); i++){
            if (lists[i])
                minHeap.push(lists[i]);
        }
        while (!minHeap.empty()){
            if (minHeap.top()->next){
                minHeap.push(minHeap.top()->next);
            }
            p->next = minHeap.top();
            p = p->next;
            minHeap.pop();
        }
        return ans->next;
    }
};

合并区间

合并区间

​ • 题目链接： LeetCode 56. Merge Intervals

​ • 思路： 虽然这道题不直接使用优先队列，但它的思想和堆排序有相似之处。首先对区间进行排序，然后合并重叠的区间。

我的做法使用了优先队列，两个小顶堆的做法虽然改变了原来的区间对应关系，但是对结果没有影响。当然，想来最好的做法还是先排序再遍历去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> ans;
    priority_queue<int,vector<int>, greater<int>> pq1;
    priority_queue<int, vector<int>, greater<int>> pq2;
    for (int i = 0; i < intervals.size(); i++){
        pq1.push(intervals[i][0]);
        pq2.push(intervals[i][1]);
    }
    while (!pq1.empty()){
        int a = pq1.top();
        pq1.pop();
        while (!pq1.empty() && pq1.top() <= pq2.top()){
            pq1.pop();
            pq2.pop();
        }
        ans.push_back(vector<int>{a,pq2.top()});
        pq2.pop();
    }
    return ans;
}

最佳做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
      sort(intervals.begin(), intervals.end());

      vector<vector<int>> merged;
      for (auto interval : intervals) {
          // if the list of merged intervals is empty or if the current
          // interval does not overlap with the previous, simply append it.
          if (merged.empty() || merged.back()[1] < interval[0]) {
              merged.push_back(interval);
          }
          // otherwise, there is overlap, so we merge the current and previous
          // intervals.
          else {
              merged.back()[1] = max(merged.back()[1], interval[1]);
          }
      }
      return merged;
  }
};