前K个高频元素

[Musings]
开始设计模式的日子了,先从K个高频的算法题开始,慢慢来

原体https://leetcode.cn/problems/g5c51o/description/

先本能写第一版,按照最普通的思路

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
29
function topKFrequent(nums: number[], k: number): number[] {
    let sortMap = new Map();
    //最简单的版本就是先跑出来,便利数组,然后计算出现次数
    //时间复杂度O(n),做一遍traversal
    nums.forEach(val => {
        let target = sortMap.get(val);
        if (target) {
            sortMap.set(val, ++target);
        } else {
            sortMap.set(val, 1);
        }
    })
    let result = [];
    //遍历k次获取最高频元素,因为map没法排序
    //时间复杂度O(k),做k次遍历,所以时间复杂度为O(n*k)
    for (let i = 0; i < k; i++) {
        let valS = -Infinity;
        let keyS = -Infinity;
        sortMap.forEach((val, key) => {
            if (val > valS) {
                valS = val;
                keyS = key
            }
        })
        sortMap.delete(keyS);
        result.push(keyS);
    }
    return result;
};

以上的时间复杂度是O(n k),现在开始优化第一版,主要的额思路就是使用array的内部排序这样复杂度降低到O(n logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function topKFrequent(nums: number[], k: number): number[] {
    let sortMap = new Map<number, number>();
    for (const val of nums) {
        sortMap.set(val, (sortMap.get(val) || 0) + 1);
    }
    //这里的内置排序用的是O(logn)复杂度的,所以这里的复杂度是O(n*logn)
    //这里更多的注意点就是熟练使用内部的操作符来简化代码,提高可读性
    const sorted = Array.from(sortMap.entries())
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(entry => entry[0]);
    return sorted;
};

最后考虑堆化,排序么,自然而然想到堆化

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
function topKFrequent3(nums: number[], k: number): number[] {
    let map = new Heap();
    let sortMap = new Map<number, number>();
    for (const val of nums) {
        sortMap.set(val, (sortMap.get(val) || 0) + 1);
    }
    for (const pair of sortMap.entries()) {
        map.push(pair)
    }
    let res: number[] = [];
    for (let i = 0; i < k; i++) {
        res.push(map.pop()[0]);
    }
    return res;
}

//ts默认没有堆,所以日常手撕一个,顺便适应下这个题目,所以每个元素都是数组
class Heap {
    private maxHeap: [number, number][];
    constructor() {
        this.maxHeap = [];
    }
    push(val: [number, number]) {
        this.maxHeap.push(val);
        let curInd = this.size() - 1;
        while (true) {
            let parentInd = this.parent(curInd);
            if (parentInd < 0) {
                break;
            }
            let parentVal = this.maxHeap[parentInd];
            if (parentVal[1] < val[1]) {
                this.swap(parentInd, curInd);
                curInd = parentInd;
            } else {
                break;
            }
        }
    }
    swap(i: number, j: number) {
        let temp = this.maxHeap[i];
        this.maxHeap[i] = this.maxHeap[j];
        this.maxHeap[j] = temp;
    }
    peek() {
        return this.maxHeap[0];
    }
    pop() {
        const res = this.maxHeap[0];
        this.swap(0, this.size() - 1);
        this.maxHeap.pop();
        if (this.size() == 0) return res;
        let currentInd = 0;
        while (true) {
            let val = this.maxHeap[currentInd][1];
            let left = this.maxHeap[this.left(currentInd)];
            let right = this.maxHeap[this.right(currentInd)];
            let maxInd;
            if (left == undefined) break;
            if (right == undefined) maxInd = this.left(currentInd);
            else {
                maxInd = right[1] > left[1] ? this.right(currentInd) : this.left(currentInd);
            }
            if (maxInd < 0 || this.maxHeap[maxInd][1] < val) break;
            this.swap(currentInd, maxInd);
            currentInd = maxInd;
        }
        return res;
    }
    size() {
        return this.maxHeap.length;
    }
    isEmpty() {
        return this.size() == 0;
    }
    left(i: number) {
        let ind = 2 * i + 1;
        return ind >= this.size() ? -1 : ind;
    }
    right(i: number) {
        let ind = 2 * i + 2;
        return ind >= this.size() ? -1 : ind;
    }
    parent(i: number) {
        return Math.floor((i - 1) / 2);
    }
}

今天就到这吧,拉闸!