Leetcode - 347. Top K Frequent Elements

soopsaram·2022년 5월 9일
0

목록 보기
19/85

문제

주어진 배열에 동일한 요소 갯수가 많은 순서대로 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;
}
기록 & 정리 아카이브 용도 (보다 완성된 글은 http://soopsaram.com/documentudy)