kali做钓鱼网站,wordpress禁止自适应,wordpress store,怎么把产品快速宣传并推广原题链接#x1f517;#xff1a;前 K 个高频元素 难度#xff1a;中等⭐️⭐️
题目
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2]
示例 2…原题链接前 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 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的
进阶你所设计算法的时间复杂度 必须 优于 O(n log n) 其中 n 是数组大小。
堆 堆Heap是一种特殊的树状数据结构它满足两个主要特性 结构性堆通常是一棵完全二叉树这意味着除了最后一层外其他每一层都被完全填满并且最后一层的节点尽可能地集中在左侧。 堆属性堆中的每一个节点都必须满足特定的顺序要求这个要求可以是最大堆属性或最小堆属性。 最大堆任何一个父节点的值都大于或等于它的子节点的值。这意味着堆的根节点是所有节点中的最大值。最小堆任何一个父节点的值都小于或等于它的子节点的值。这意味着堆的根节点是所有节点中的最小值。 堆在计算机科学中广泛应用于各种算法和数据结构特别是在需要快速访问最大元素或最小元素的场景中。例如堆排序算法、优先队列的实现等。 在编程语言中堆通常通过优先队列Priority Queue这种抽象数据类型来实现。优先队列允许快速地插入新元素和删除或检索最大或最小元素。 堆的常见操作包括 插入Push向堆中添加一个新元素。删除最大/最小元素Pop移除并返回堆中的最大或最小元素。查找最大/最小元素Peek/Top返回堆中的最大或最小元素但不从堆中移除它。 堆的实现可以通过数组来完成其中每个元素的索引和其父节点或子节点的索引之间有一定的数学关系。例如在数组表示的堆中一个元素的父节点可以通过(i-1)/2计算得到其中i是该元素的索引其子节点可以通过2*i 1左子节点和2*i 2右子节点计算得到。 题解
解题思路 数组中的第K个最大元素是LeetCode上的一道经典题目它要求在给定的未排序数组中找到第K个最大的元素。以下是解题的几种思路 排序 思路首先对数组进行排序然后直接访问数组的倒数第K个位置的元素。复杂度时间复杂度为O(n log n)空间复杂度为O(1)如果使用原地排序算法。 快速选择Quick Select 思路这是快速排序算法的变种。选择一个枢纽pivot元素将数组分为两部分一部分包含比枢纽小的元素另一部分包含比枢纽大的元素。然后根据枢纽的位置来决定是继续在左侧还是右侧搜索第K个最大元素。复杂度平均时间复杂度为O(n)最坏情况已排序数组为O(n^2)。 堆优先队列 思路 使用最小堆维护一个大小为K的最小堆遍历数组对于每个元素如果堆未满则直接加入如果堆满了且当前元素大于堆顶元素则替换堆顶元素。使用最大堆维护一个大小为n的堆遍历数组对于每个元素如果堆未满则直接加入如果堆满了且当前元素小于堆顶元素则不加入。最后堆顶元素是第K大的元素但这种方法需要O(n)空间。 复杂度时间复杂度为O(n log K)空间复杂度为O(K)。 BFPRT算法中位数的中位数算法 思路这是一种选择算法用于找到未排序数组的第K小或第K大元素。它首先找到一组“候选”元素然后递归地在这组候选元素中找到中位数直到找到第K小的元素。复杂度平均时间复杂度为O(n)。 线性时间选择算法 思路这是一种基于随机化的算法通过随机选择枢纽元素来减少最坏情况的发生概率。复杂度期望时间复杂度为O(n)。 c demo
#include iostream
#include vector
#include unordered_map
#include algorithm// 自定义比较函数首先按频率降序频率相同则按元素值升序
bool compare(const std::pairint, int a, const std::pairint, int b) {if (a.second b.second) {return a.first b.first;}return a.second b.second;
}std::vectorint topKFrequent(const std::vectorint nums, int k) {std::unordered_mapint, int freqMap;for (int num : nums) {freqMap[num];}std::vectorstd::pairint, int freqList;for (const auto kv : freqMap) {freqList.emplace_back(kv.first, kv.second);}// 根据频率和元素值排序std::sort(freqList.begin(), freqList.end(), compare);// 选择前 K 个元素std::vectorint result;for (int i 0; i k; i) {result.push_back(freqList[i].first);}return result;
}int main() {std::vectorint nums { 1, 1, 1, 2, 2, 3 };int k 2;std::vectorint result topKFrequent(nums, k);std::cout The k most frequent elements are: ;for (int num : result) {std::cout num ;}std::cout std::endl;return 0;
}输出结果 The 2 most frequent elements are: 1 2 代码仓库地址topKFrequent
