Leetcode - 347. Top K Frequent Elements

문제

주어진 배열에 동일한 요소 갯수가 많은 순서대로 k개 출력.
https://leetcode.com/problems/top-k-frequent-elements/

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

해결 O(K logN)

해시테이블과 heap을 모두 직접 구현해 풀어서 intense 했다.
Leetcode 에서 100번째로 해결한 문제라서 특별했던 문제!

#include <stdlib.h>

struct elem {
    int num;
    int cnt;
    struct elem *next;
};

struct pq {
    int heap_size;
    struct elem *heap;
};
struct pq *q;

#define HSIZE 100001
struct elem *table[HSIZE];

unsigned int hash(int val)
{
    return (unsigned int)val % HSIZE;
}

/* search and create an elelment in hash table */
struct elem *hash_add_create(int num, int create)
{
        struct elem *node;
        unsigned int hashval = hash(num);
        for (node = table[hashval]; node != NULL; node = node->next)
                if (node->num == num)
                        return node;
        if (create) {
                node = (struct elem*)malloc(sizeof(struct elem));
                node->num = num;
                node->cnt = 0;
                node->next = table[hashval];
                table[hashval] = node; /* add at the 1st position */
        }   
        return node;
}

void swap(struct elem *arr, int a, int b)
{
    struct elem temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void heapify_down(struct elem arr[], int p_idx, int size)
{
    int largest = p_idx;
    int l_idx = p_idx * 2 + 1;
    int r_idx = p_idx * 2 + 2;
    
    if (l_idx < size && arr[l_idx].cnt > arr[largest].cnt)
        largest = l_idx;
    if (r_idx < size && arr[r_idx].cnt > arr[largest].cnt)
        largest = r_idx;
    if (largest != p_idx) {
        //swap(arr, largest, p_idx);
        struct elem temp = arr[largest];
        arr[largest] = arr[p_idx];
        arr[p_idx] = temp;
        heapify_down(arr, largest, size);
    }
}

void build_heap(void)
{
    for (int i = q->heap_size / 2 - 1; i >= 0; i--)
        heapify_down(q->heap, i, q->heap_size);
}

int pop_heap(struct elem arr[])
{
    int ret = arr[0].num;
    q->heap_size--;
    arr[0] = arr[q->heap_size];
    heapify_down(arr, 0, q->heap_size);
    return ret;
}

void print_heap()
{
    for (int i = 0; i < q->heap_size; i++)
        printf("(%d,%d)", q->heap[i].num,q->heap[i].cnt);
    printf("\n");
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    *returnSize = k;
    int hsize = numsSize;
    int num_cnt = 1;
    
    memset(table, NULL, sizeof(struct elem *) * HSIZE);
    q = (struct pq*)calloc(1, sizeof(struct pq));
    q->heap = (struct elem *)calloc(hsize, sizeof(struct elem));
    
    /* generate hash table */
    for (int i = 0; i < numsSize; i++) {  // O(n)
        struct elem *tmp = hash_add_create(nums[i], 1);
        tmp->cnt++;
    }
    /* get num & cnt of num, push to heap */
    for (int i = 0; i < HSIZE; i++) { // O(n)
        struct elem *node;
        unsigned int hashval = hash(i);
        for (node = table[hashval]; node != NULL; node = node->next) {
            if (node && node->cnt) {
                q->heap[q->heap_size].num = node->num;
                q->heap[q->heap_size].cnt = node->cnt;
                q->heap_size++;
            }
        }
    }
    /* get k max values */
    build_heap(); // O(n)
    for (int i = 0; i < k; i++) // O(k logn)
        nums[i] = pop_heap(q->heap);
    return nums;
}