347. Top K Frequent Elements

Top K Frequent Elements - LeetCodeLeetCode

Bucket sort

time: O(n)

space: O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const ans = [];
    const memo = {};
    for (const num of nums) {
        if (memo[num] === undefined) memo[num] = 0;
        memo[num]++;
    }

    const bucket = new Array();
    for (const [key, cnt] of Object.entries(memo)) {
        if (bucket[cnt] === undefined) {
            bucket[cnt] = [];
        }
        bucket[cnt].push(key);
    }

    let cnt = 0;
    for (let i = bucket.length - 1; i >= 0; i--) {
        if (cnt >= k) break;

        const arr = bucket[i];
        if (arr !== undefined) {
            ans.push(...arr);
            cnt += arr.length;
        }
    }

    return ans;
};

Min Heap

time: O(nlogn)

space: O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
    const answer = [];

    const memo = {};
    for (const num of nums) {
        if (memo[num] === undefined) memo[num] = 0;
        memo[num]++;
    }

    const arr = Object.entries(memo);
    const minHeap = new MinHeap(arr, (a, b) => a[1] > b[1]);

    let cnt = 0;
    while (cnt < k) {
        const [v] = minHeap.remove();
        answer.push(v);
        cnt++;
    }

    return answer;
};

class MinHeap {
    constructor(arr, predicate = (a, b) => a < b) {
        this.predicate = predicate;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }
        return arr;
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;

        while (left <= endIndex) {
            let min = left;
            let right = currentIndex * 2 + 2;
            if (heap[right] && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            if (this.predicate(heap[currentIndex], heap[min])) break;
            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor((currentIndex  - 1) / 2);
        while (parentIndex >= 0) {
            const flag = this.predicate(heap[parentIndex], heap[currentIndex]);
            if (flag) break;
            this.swap(heap, currentIndex, parentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex  - 1) / 2);
        }
    }

    insert(value) {
        this.heap.push(value);
        this.siftUp(this.heap, this.heap.length - 1);
    }

    remove() {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;        
    }

    swap(arr, a, b) {
        const temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        return arr;
    }
}