题目:
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
输入: nums = [1], k = 1
输出: [1]
抛砖引玉
思路
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {
let map = new Map(),
arr = []
for (let i = 0; i < nums.length; i++) {
if (map.has(nums[i])) {
let val = map.get(nums[i])
map.set(nums[i], ++val)
} else {
map.set(nums[i], 1)
arr.push(nums[i])
}
}
let sortArr = arr.sort((a, b) => map.get(b) - map.get(a))
return sortArr.splice(0, k)
}
var topKFrequent = function (nums, k) {
let map = new Map(),
heap = [],
arr = []
for (let i = 0; i < nums.length; i++) {
if (map.has(nums[i])) {
let val = map.get(nums[i])
map.set(nums[i], ++val)
} else {
map.set(nums[i], 1)
arr.push(nums[i])
}
}
if (map.size <= k) return arr
for (let [key, value] of map) {
if (heap.length < k) {
heap.push(key)
// 堆内放够k个元素后,对前k个元素堆化(即根据出现频率从小到大排列)
buildHeapIn(heap.length - 1);
} else if (map.get(heap[0]) < value) {
// 出现大于堆顶的元素则替换掉对顶,并且重新对新的堆排序
heap[0] = key
buildHeapOut(0);
}
}
// 添加元素重新排序
function buildHeapIn(x) {
while (x > 0) {
let y = parseInt((x - 1)/2,10);
if (map.get(heap[y]) > map.get(heap[x])) {
swap(heap,y, x);
x = y;
} else {
break;
}
}
}
// 替换元素重新排序
function buildHeapOut(x) {
while (2 * x + 1 < heap.length) {
let y = 2 * x + 1;
if (y + 1 < heap.length && map.get(heap[y+1]) < map.get(heap[y])) {
y++;
}
if ( map.get(heap[x]) > map.get(heap[y])) {
swap(heap,x, y);
x = y;
} else {
break;
}
}
}
// 替换元素
function swap(arr, i, j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
return heap.reverse()
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = (nums, k) => {
let map = new Map(),
heap = [],
arr = [],
_result = []
ValueKey = [];
// 哈希
for (let i = 0; i < nums.length; i++) {
if (map.has(nums[i])) {
let val = map.get(nums[i])
map.set(nums[i], ++val)
} else {
map.set(nums[i], 1)
arr.push(nums[i])
}
}
if (map.size <= k) return arr
// 索引
for (let [key, value] of map) {
if (!ValueKey[value]) {
ValueKey[value] = [key];
} else {
ValueKey[value].push(key)
}
}
// 从后向其取k个元素
for (let i = ValueKey.length - 1; i >= 0; i--) {
if (_result.length < k && ValueKey[i]) {
_result = _result.concat(ValueKey[i])
} else {
continue
}
}
return _result;
};