leetcode链接:https://leetcode.cn/problems/top-k-frequent-elements/
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示:
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
进阶: 你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
更多详细内容,请微信搜索“前端爱好者
“, 戳我 查看 。
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
let map = new Map() // 定义一个map类型
let arr = [...new Set(nums)] // 获取数组去重后的元素
// 一次遍历nums值,把他们出现的频次放在map里面
nums.map(num => {
if(map.has(num)){
map.set(num,map.get(num) + 1)
} else {
map.set(num,1)
}
})
// 现针对去重元素进行排序
return arr.sort((a,b) => {
map.get(b) - map.get(a)
}).slice(0,k)
};
桶排序适用 top k中 频次题,计数排序适用 top k中 值的题
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
// 桶排序 原理:1. 将数据滑倒到有限个桶里面,再将桶进行排序
// 用map存储频次,用数组表达桶,频次作为数据下表表达,针对不同的频次的熟悉,聚合
var topKFrequent = function(nums, k) {
let map = new Map() // 定义一个map类型
// 一次遍历nums值,把他们出现的频次放在map里面
nums.map(num => {
if(map.has(num)){
map.set(num,map.get(num) + 1)
} else {
map.set(num,1)
}
})
if(map.size <=k ){
return [...map.keys()]
}
return bucketSort(map,k)
};
// 桶排序内容
const bucketSort = (map,k) => {
let arr = []
let res = [] //结果
// 针对map中每个元素遍历
map.forEach((value,key) => {
// 可以利用频次作为下标,降数据分配到桶里
if(!arr[value]) {
arr[value] = [key]
} else {
arr[value].push(key)
}
})
// 倒序排列
for(let i = arr.length -1 ; i >=0 && res.length < k ;i-- ){
if(arr[i]){
res.push(...arr[i])
}
}
return res
}
leetcode地址:https://leetcode.cn/problems/kth-largest-element-in-an-array/
给定整数数组 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
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
nums.sort((a,b) => b-a ).slice(0,k)
return nums[k -1]
};
快速排序:本质是:拆分,分而治之
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
// 快速排序 分而治之
// 1. 找到基准值
// 1. 比他大的房右边,小的放左边
// 3. 按照1 2 步骤继续拆分,直到找到下标
// 创建指针,左右两端
// 1. 左侧index 大于 右侧指针index
quickSort(nums)
return nums[nums.length - k]
};
// 快排
let quickSort = (arr) => {
quick(arr,0,arr.length -1) // 基准:数组,起始值(开始指针),终止值(结束指针)
}
const quick = (arr, left,right)=>{
let index;
if(left < right){
index = partition(arr, left,right)
// 左侧小于基准值
if(left < index - 1){
quick(arr,left,index - 1 )
}
if(index < right){
quick(arr,index,right)
}
}
}
// 找基准值
const partition = (arr, left,right)=>{
let datum = arr[Math.floor(Math.random() * (right - left + 1)) + left] // 基准值
let i = left // 左侧
let j = right // 右侧
while ( i <= j){
// 左侧
while(arr[i] < datum){
i ++
}
// 右侧
while(arr[j] > datum){
j --
}
if( i <= j ){
[arr[i],arr[j]] = [arr[j],arr[i]] // 注意这里
i+=1
j-=1
}
}
return i
}
桶排序(Bucket Sort)是一种基于分治思想的排序算法。
它的基本思想是将要排序的数据分到几个有序的桶中,每个桶里的数据再单独进行排序。通常情况下,桶的数量是根据数据的分布情况来决定的。
桶排序的过程可以描述如下:
桶排序的时间复杂度为O(n),但需要额外的空间来存储桶。在数据分布均匀的情况下,桶排序的效率很高,但如果数据分布不均匀,则可能会导致某些桶的大小远远超过其他桶,从而导致效率降低。
桶排序适用于数据范围不大的情况下,且数据分布均匀的情况下效率最高。在实际应用中,桶排序通常被用于外部排序,即当待排序数据无法全部载入内存时,先将数据分割成若干个能够装入内存的部分,对每部分进行排序,最后再将它们合并起来。
下面举一个例子来说明桶排序的过程:
假设有一个待排序的数组[3, 6, 1, 8, 2, 5, 7, 4],现在我们要使用桶排序对其进行排序,具体步骤如下:
因此,桶排序的时间复杂度为O(n),但需要额外的空间来存储桶。在数据分布均匀的情况下,桶排序的效率很高,但如果数据分布不均匀,则可能会导致某些桶的大小远远超过其他桶,从而导致效率降低。
快速排序(Quick Sort)是一种常用的排序算法,它通过将一个数组分割成两个子数组来进行排序。具体而言,快速排序选择一个基准元素(pivot),将数组中小于基准元素的元素放在基准元素的左边,大于基准元素的元素放在基准元素的右边,然后递归地对左右两个子数组进行排序。
假设有一个待排序的数组[8, 4, 2, 9, 3, 5, 1, 6, 7],我们使用快速排序对其进行排序,具体步骤如下:
快速排序的平均时间复杂度为O(nlogn),最坏情况下(当选择的基准元素总是数组中的最大或最小元素)的时间复杂度为O(n^2)。但由于其实现简单、性能优秀,在实际应用中被广泛使用。