aboutsummaryrefslogtreecommitdiff
path: root/top_k_freq_element.c
blob: 3fd0e092c9b6f87cc80983c5dabe6bc64309da4d (plain)
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
// 347. Top K Frequent Elements
#include "lib/uthash/src/uthash.h"
#include <stdio.h>
#include <stdlib.h>

/*
 * given an integer array 'nums' and an integer 'k', return the 'k' most
 * frequent elements you may return the right answer in any order!!!
 */

typedef struct {
  int idxs[500];
  int num_idx;
} pair;

typedef struct {
  int elem;
  int count;
  UT_hash_handle hh;
} h_elem;

int *topKFrequent(int *nums, int nums_size, int k, int *return_size) {
  h_elem *count = NULL, *s, *curr;
  pair *freq = calloc(sizeof(pair), nums_size + 1);
  int *ans = malloc(sizeof(int) * k);
  *return_size = 0;
  for (int i = 0; i < nums_size; i++) {
    HASH_FIND_INT(count, &nums[i], s);
    if (s)
      s->count++;
    else {
      s = malloc(sizeof(h_elem));
      s->elem = nums[i];
      s->count = 1;
      HASH_ADD_INT(count, elem, s);
    }
  }
  HASH_ITER(hh, count, curr, s)
  freq[curr->count].idxs[freq[curr->count].num_idx++] = curr->elem;
  for (int i = nums_size; i >= 0; i--)
    if (freq[i].num_idx)
      for (int j = 0; j < freq[i].num_idx; j++) {
        ans[(*return_size)++] = freq[i].idxs[j];
        if (*return_size == k)
          return ans;
      }
  return ans;
}

int main() {
  int n1[] = {1, 1, 1, 2, 2, 3}, n2[] = {1};
  int *r1 = topKFrequent(n1, 6, 2, NULL);
  int *r2 = topKFrequent(n2, 1, 1, NULL);
  for (int i = 0; i < 6; i++)
    printf("%d ", r1[i]);
  printf("\n%d ", r1[0]);
}