LeetCode-in-All

347. Top K Frequent Elements

Medium

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Solution

#include <stdlib.h>
#include <limits.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* topKFrequent(int* nums, int n, int k, int* returnSize) {
    if (n == 0 || k == 0) *returnSize = 0;

    int min_val = INT_MAX;
    int max_val = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] < min_val) min_val = nums[i];
        if (nums[i] > max_val) max_val = nums[i];
    }

    int range = max_val - min_val + 1;
    int offset = -min_val; 

    // creating frequency array and puttin zero inside as default 

    int* freq = (int*)malloc(range * sizeof(int));
    for (int i = 0; i < range; i++) freq[i] = 0;

    // stroing the frequency in the freq array by ++ opertor 

    for (int i = 0; i < n; i++) freq[nums[i] + offset]++;

    //  finding the k max elemts in the freq array and storing it in result array 
    int* result_1 = (int*)malloc(k * sizeof(int));

    for (int i = 0; i < k; i++) {
        int maxval = -1;
        int max_index = -1;

        for (int j = 0; j < range; j++) {
            if (freq[j] > maxval) {
                maxval = freq[j];
                max_index = j;
            }
        }

        result_1[i] = max_index - offset;
        freq[max_index] = -1;
    }

    *returnSize = k;
    free(freq);
    return result_1;
}

This site is open source. Improve this page.