hot100堆题解

215. 数组中的第K个最大元素

问题描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

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

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• $1 <= k <= nums.length <= 10^5$
• $-10^4 <= nums[i] <= 10^4$

题解

解题思路

这道题要求我们在一个无序数组中找到第 k 个最大的元素，且要求时间复杂度为 $O(n)$。我们可以采用 快速选择算法（Quickselect），这是一种基于快速排序的选择算法，平均时间复杂度为 $O(n)$，最坏时间复杂度为 $O(n^2)$，但可以通过随机化来优化。

快速选择算法的思想

1. 基于快速排序的思想：
   • 快速排序每次选择一个基准元素（pivot），并将数组划分为两部分，左边的元素都比基准小，右边的元素都比基准大。
   • 我们并不需要完全排序数组，只需找到数组中第 k 个最大元素的位置即可。
2. 快速选择的步骤：
   • 划分：选择一个基准元素，将数组分为两部分，一部分是大于基准的元素，另一部分是小于基准的元素。
   • 选择：如果第 k 个最大的元素位于基准元素的左边，递归地在左边部分继续查找；如果它位于基准元素的右边，递归地在右边部分继续查找。
3. 如何选择第 k 个最大元素：
   • 对于第 k 个最大元素，它位于排序后的数组中的位置是 n - k（0-indexed）。因此，在快速选择中我们要找到的位置是 n - k。

---

代码实现

#include <iostream>
#include <vector>
#include <cstdlib> // for rand()
#include <algorithm>

int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[right];  // 选择最右边的元素作为基准
    int i = left - 1;         // i指向小于pivot的部分的最后一个元素

    // 将比pivot小的元素移到左边，比pivot大的移到右边
    for (int j = left; j < right; ++j) {
        if (nums[j] <= pivot) {
            ++i;
            std::swap(nums[i], nums[j]);
        }
    }

    // 将基准元素放到正确的位置
    std::swap(nums[i + 1], nums[right]);
    return i + 1;
}

int quickSelect(std::vector<int>& nums, int left, int right, int k) {
    if (left <= right) {
        int pivotIndex = partition(nums, left, right);
        
        // pivotIndex 是基准元素在排序后的数组中的位置
        if (pivotIndex == k) {
            return nums[pivotIndex];
        } else if (pivotIndex < k) {
            return quickSelect(nums, pivotIndex + 1, right, k);
        } else {
            return quickSelect(nums, left, pivotIndex - 1, k);
        }
    }

    return -1;  // 这个不会被执行，因为我们保证了k是有效的
}

int findKthLargest(std::vector<int>& nums, int k) {
    int n = nums.size();
    return quickSelect(nums, 0, n - 1, n - k);  // 找到第n-k个元素，即第k个最大元素
}

int main() {
    std::vector<int> nums1 = {3, 2, 1, 5, 6, 4};
    int k1 = 2;
    std::cout << "Example 1: " << findKthLargest(nums1, k1) << std::endl;  // 输出 5

    std::vector<int> nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    int k2 = 4;
    std::cout << "Example 2: " << findKthLargest(nums2, k2) << std::endl;  // 输出 4

    return 0;
}

---

代码解释

1. partition函数：
   • 这个函数将数组分为两部分：小于等于基准的部分和大于基准的部分，并返回基准元素在排序后的数组中的位置。
   • 我们选择数组中的最后一个元素作为基准元素。
2. quickSelect函数：
   • 该函数递归地查找数组中的第 k 个元素。首先调用 partition 函数，将数组分成两部分。然后判断第 k 个元素是在基准元素的左边还是右边：
     • 如果在左边，递归地继续在左边查找。
     • 如果在右边，递归地继续在右边查找。
     • 如果基准元素就是目标元素，直接返回该元素。
3. findKthLargest函数：
   • 这是主要的函数，接收输入数组 nums 和要找的第 k 个最大元素，调用 quickSelect 来找到并返回该元素。
4. main函数：
   • 在 main 中，提供了两个示例，分别输出了数组中第 k 个最大元素的值。

---

时间复杂度和空间复杂度

• 时间复杂度：
  • 平均情况下：$O(n)$，每次划分都会将数组分成两部分，递归的深度为 $O(\log n)$，每次划分的复杂度为 $O(n)$，因此总的时间复杂度为 $O(n)$。
  • 最坏情况下：$O(n^2)$，即每次划分都无法均匀分割（类似于最坏情况下的快速排序），但这种情况通过随机化基准元素可以减少。
• 空间复杂度：$O(1)$，因为我们只使用了常数空间进行交换，不需要额外的空间存储数据。

---

示例解析

示例 1

输入：[3, 2, 1, 5, 6, 4] 和 k = 2

1. n = 6，目标是找第 2 大的元素，即排序后的数组中的第 4 个元素。
2. 通过快速选择，我们逐步缩小搜索范围，最终找到元素 5。

示例 2

输入：[3, 2, 3, 1, 2, 4, 5, 5, 6] 和 k = 4

1. n = 9，目标是找第 4 大的元素，即排序后的数组中的第 5 个元素。
2. 通过快速选择，我们最终找到元素 4。

347. 前K个高频元素

问题描述

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

示例 1:

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

示例 2:

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

提示：

• $1 <= nums.length <= 10^5$
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

题解

解题思路

这道题要求返回数组中出现频率前 k 高的元素，并且要求算法的时间复杂度优于 $O(n \log n)$，因此我们需要寻找比排序更高效的方法。我们可以使用 堆（特别是小根堆）来帮助我们解决问题。

步骤分析

1. 计算频率：
   • 首先，我们可以使用哈希表（unordered_map）来计算数组中每个元素的出现频率。哈希表的构建时间复杂度为 $O(n)$。
2. 使用堆：
   • 我们需要找出频率前 k 高的元素。可以使用一个小根堆来存储频率最高的 k 个元素。
   • 小根堆的大小固定为 k，这样堆顶始终存储的是频率最低的元素。如果当前元素的频率大于堆顶元素的频率，就将堆顶元素移除，并将当前元素添加到堆中。这样，最终堆中的元素就是频率最高的 k 个元素。
3. 堆的操作：
   • 将元素及其频率作为堆的元素，按照频率从小到大的顺序存储。堆的操作时间复杂度是 $O(\log k)$，因此总的时间复杂度为 $O(n \log k)$，比 $O(n \log n)$ 更高效。

代码实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    // 统计每个数字的频率
    unordered_map<int, int> freqMap;
    for (int num : nums) {
        freqMap[num]++;
    }

    // 使用小根堆存储频率最高的k个元素
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    
    for (auto& entry : freqMap) {
        minHeap.push({entry.second, entry.first});
        if (minHeap.size() > k) {
            minHeap.pop();  // 保证堆中只有k个元素
        }
    }

    // 从堆中取出前k个频率最高的元素
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }

    return result;
}

int main() {
    vector<int> nums1 = {1,1,1,2,2,3};
    int k1 = 2;
    vector<int> result1 = topKFrequent(nums1, k1);
    cout << "Example 1: ";
    for (int num : result1) {
        cout << num << " ";
    }
    cout << endl;  // 输出: [1, 2]

    vector<int> nums2 = {1};
    int k2 = 1;
    vector<int> result2 = topKFrequent(nums2, k2);
    cout << "Example 2: ";
    for (int num : result2) {
        cout << num << " ";
    }
    cout << endl;  // 输出: [1]

    return 0;
}

代码解释

1. 统计频率：
   • 使用一个哈希表 freqMap 来记录每个元素的频率。遍历 nums 数组，将每个元素的频率存入哈希表中。
2. 使用小根堆：
   • 我们创建一个小根堆 minHeap，堆中存储的是元素及其对应的频率。堆的元素类型是 pair<int, int>，其中第一个元素是频率，第二个元素是数字。
   • 遍历频率表，将每个元素加入堆中。如果堆的大小超过 k，则弹出堆顶元素，保证堆中始终存储频率最高的 k 个元素。
3. 提取结果：
   • 最后，我们从堆中取出元素，得到频率前 k 高的元素。由于堆顶元素的顺序是从小到大，我们可以将结果存入一个数组并返回。

时间复杂度分析

• 统计频率：遍历一次数组，时间复杂度为 $O(n)$，其中 n 是数组的大小。
• 堆操作：对于每个元素，我们进行插入操作，堆的大小最大为 k，插入操作的时间复杂度为 $O(\log k)$。因此，遍历频率表并进行堆操作的时间复杂度为 $O(n \log k)$。
• 提取结果：我们从堆中取出 k 个元素，时间复杂度为 $O(k \log k)$，但这部分通常可以认为是常数操作。

综合来看，总的时间复杂度为 $O(n \log k)$。

空间复杂度分析

• 频率哈希表：我们需要一个哈希表来存储元素及其频率，空间复杂度为 $O(n)$。
• 小根堆：堆中最多存储 k 个元素，空间复杂度为 $O(k)$。

因此，空间复杂度为 $O(n + k)$。

示例解析

示例 1

输入：[1, 1, 1, 2, 2, 3] 和 k = 2

• 频率统计结果为 {1: 3, 2: 2, 3: 1}。
• 使用小根堆来存储前 2 个频率最高的元素，最终得到 [1, 2]。

示例 2

输入：[1] 和 k = 1

• 频率统计结果为 {1: 1}。
• 由于只有一个元素，结果为 [1]。

总结

• 我们通过使用哈希表计算元素频率，再利用小根堆高效地找到频率前 k 高的元素，时间复杂度为 $O(n \log k)$，符合题目要求。

295. 数据流的中位数

问题描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 $10^-5$ 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

• $-10^5 <= num <= 10^5$
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 $5 * 10^4$ 次调用 addNum 和 findMedian

题解

解题思路

要解决这个问题，我们需要有效地处理动态数据流的中位数查询。我们可以通过维护两个堆来解决这个问题。一个大根堆和一个小根堆将帮助我们在每次插入数据后快速获取当前的中位数。

核心思想

1. 使用两个堆：

   • 大根堆（maxHeap）：用于存储数据流中较小的一半元素。
   • 小根堆（minHeap）：用于存储数据流中较大的一半元素。

   堆的性质：

   • 大根堆的堆顶元素是当前较小部分的最大值。
   • 小根堆的堆顶元素是当前较大部分的最小值。

2. 如何保持两个堆的平衡：

   • 如果数据流中元素的数量是奇数，两个堆的大小差距为 1，即一个堆有比另一个堆多一个元素。
   • 如果数据流中元素的数量是偶数，两个堆的大小相等。

3. 插入元素：

   • 每次插入元素时，将元素插入适当的堆，并保持堆的大小平衡。
   • 如果插入到大根堆，需要确保大根堆中的最大元素不大于小根堆中的最小元素。

4. 查询中位数：

   • 如果两个堆的大小相等，中位数为两个堆的堆顶元素的平均值。
   • 如果堆的大小不等，中位数就是堆顶元素较多的那个堆的堆顶元素。

代码实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class MedianFinder {
public:
    MedianFinder() {
        // 小根堆用于存储较大的一半元素
        // 大根堆用于存储较小的一半元素
    }

    void addNum(int num) {
        // 将新元素加入大根堆（存储较小的部分）
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }

        // 保证两个堆的大小平衡
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double findMedian() {
        // 如果两个堆的大小相等，返回两个堆顶元素的平均值
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        }
        // 如果大根堆的大小更大，则中位数就是大根堆的堆顶元素
        return maxHeap.top();
    }

private:
    priority_queue<int> maxHeap; // 大根堆，用于存储较小的部分
    priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆，用于存储较大的部分
};

int main() {
    MedianFinder medianFinder;
    
    medianFinder.addNum(1);    // arr = [1]
    medianFinder.addNum(2);    // arr = [1, 2]
    cout << medianFinder.findMedian() << endl; // 1.5

    medianFinder.addNum(3);    // arr = [1, 2, 3]
    cout << medianFinder.findMedian() << endl; // 2.0

    return 0;
}

代码解释

1. MedianFinder 类的初始化：
   • maxHeap 用于存储数据流中较小的部分（实现为大根堆）。
   • minHeap 用于存储数据流中较大的部分（实现为小根堆）。
2. addNum 方法：
   • 通过检查当前值是否小于或等于大根堆的堆顶元素，决定将该值插入到哪个堆中。
   • 然后，调整两个堆的大小，确保它们的大小差不超过 1。如果大根堆的大小超过小根堆，则将大根堆的堆顶元素移到小根堆；如果小根堆的大小超过大根堆，则将小根堆的堆顶元素移到大根堆。
3. findMedian 方法：
   • 如果两个堆的大小相等，则返回两个堆顶元素的平均值。
   • 如果大根堆的大小大于小根堆，则返回大根堆的堆顶元素。

时间复杂度

• addNum 方法：每次插入元素需要进行堆的插入和调整操作。插入操作的时间复杂度为 $O(\log n)$，其中 n 是当前数据流中的元素数量。
• findMedian 方法：获取堆顶元素的时间复杂度为 $O(1)$。

因此，addNum 的时间复杂度为 $O(\log n)$，findMedian 的时间复杂度为 $O(1)$。

空间复杂度

我们使用了两个堆来存储数据流，因此空间复杂度为 $O(n)$，其中 n 是数据流中的元素数量。

示例解析

示例 1

输入：

["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

• addNum(1)：大根堆：[1]，小根堆：[]。
• addNum(2)：大根堆：[1]，小根堆：[2]。
• findMedian()：两个堆的大小相等，中位数为 (1 + 2) / 2 = 1.5。
• addNum(3)：大根堆：[2, 1]，小根堆：[3]。
• findMedian()：大根堆的堆顶元素为 2，中位数为 2.0。

总结

我们通过使用两个堆来维护数据流中的中位数，确保每次插入元素后都能在常数时间内获取当前的中位数，达到高效的性能。