Problem - Leetcode
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 <= 10<sup>5</sup>
-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
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.
Answer-1 in Golang
func topKFrequent(nums []int, k int) []int {
countMap := map[int]int{}
for _, num := range nums {
if count, ok := countMap[num]; ok {
countMap[num] = count + 1
} else {
countMap[num] = 1
}
}
countSlice := make([][]int, len(nums)+1)
for num, count := range countMap {
countSlice[count] = append(countSlice[count], num)
}
res := []int{}
for i := len(countSlice) - 1; i > 0; i-- {
res = append(res, countSlice[i]...)
if len(res) == k {
return res
}
}
return res
}
This code defines a Go function called topKFrequent
takes a slice of integer nums
and an integer k
as its parameters. The goal of this function is to find the k
most frequent numbers from the input slice and return them in an output slice.
Here's how the code works:
countMap := map[int]int{}
- This initializes an empty map called
countMap
. The keys of this map will be the unique numbers from the input slice, and the values will be the frequency (count) of each number.
- This initializes an empty map called
Loop through
nums
to populatecountMap
:The loop iterates through each number
num
in the input slicenums
.If
num
is already a key incountMap
, it increments the count by 1.If
num
is not a key incountMap
, it addsnum
to the map with a count of 1.
countSlice := make([][]int, len(nums)+1)
- This creates a 2D slice called
countSlice
. The outer slice will store lists of numbers grouped by their frequency. The inner slices will store the actual numbers.
- This creates a 2D slice called
Loop through
countMap
to populatecountSlice
:The loop iterates through each key-value pair in
countMap
.It appends the number (
num
) to the inner slice corresponding to its frequency (count
) incountSlice
.
Retrieve the
k
most frequent numbers:- The code initializes an empty result slice called
res
.
- The code initializes an empty result slice called
Iterate through
countSlice
in reverse order:Starting from the highest possible frequency (length of
countSlice
- 1), it iterates in reverse.It appends the numbers in the current frequency group to the result slice
res
.If the length of
res
becomes equal to or greater thank
, it means the requiredk
most frequent numbers have been found, so the function returnsres
.
If the loop completes without finding
k
most frequent numbers:- If the loop completes without returning, it means the total number of unique numbers is less than
k
. In this case, it just returns theres
slice.
- If the loop completes without returning, it means the total number of unique numbers is less than
In summary, this code calculates the frequency of each number in the input slice, groups the numbers based on their frequency, and returns the k
most frequent numbers. The approach is based on using a frequency map and a frequency-based grouping in a 2D slice.
Answer-2 Top Runtime in Golang
import (
"math"
"sort"
)
func topKFrequent(nums []int, k int) []int {
n := len(nums)
if n < 2 {
return nums
}
min, max := math.MaxInt32, math.MinInt32
for _, val := range nums {
if min > val {
min = val
}
if max < val {
max = val
}
}
numRange := max - min
//[counter, index-to-next]
allCounters := make([][2]int, numRange+2)
firstValue := nums[0]
prevValue := firstValue - min +1
diffCount := 1
allCounters[prevValue][0] = 1
allCounters[prevValue][1] = -1
for _, val := range nums[1:] {
realVal := val - min + 1
allCounters[realVal][0] += 1
if allCounters[realVal][1] == 0 {
diffCount++
allCounters[realVal][1] = prevValue
prevValue = realVal
}
}
allPairs := make([][2]int, diffCount)
//fmt.Printf("#count: %v\n", diffCount)
idx := 0
for diffCount > 0 {
val := prevValue + min - 1
allPairs[idx][0] = allCounters[prevValue][0]
allPairs[idx][1] = val
prevValue = allCounters[prevValue][1]
idx++
diffCount--
}
sort.Slice(allPairs, func(i, j int) bool {
return allPairs[i][0] > allPairs[j][0]
})
res := make([]int, k)
idx = 0
for idx < k {
res[idx] = allPairs[idx][1]
idx++
}
return res
}
This code defines a function topKFrequent
that takes an array of integers nums
and an integer k
as input and returns an array containing the top K most frequent elements in the input array. Let's break down the code step by step:
The
import
statements: The code imports the necessary packagesmath
andsort
for mathematical operations and sorting, respectively.Function
topKFrequent
: This function calculates the top K most frequent elements in thenums
array.Calculating the length of the input array: The variable
n
stores the length of thenums
array.Handling edge cases: If the length of the array is less than 2, the function returns the original array as there won't be any "top K frequent" elements.
Finding the minimum and maximum values in the array: This loop iterates through the
nums
array and finds the minimum (min
) and maximum (max
) values.Calculating the range of values: The variable
numRange
calculates the range of values in the array by subtracting the minimum from the maximum value.Initializing an array for counters and indices: The
allCounters
array is created to store two values for each element: its frequency count and the index of the next element with the same frequency.Initializing variables:
firstValue
holds the value of the first element in the array.prevValue
is initialized with the adjusted value of the first element based on the minimum value.diffCount
keeps track of the number of unique frequencies encountered.
Storing frequency and index information:
The frequency of the first element is set to 1 in
allCounters
.The index of the next element with the same frequency is set to -1.
Iterating through the array to count frequencies and indices:
This loop iterates through the
nums
array starting from the second element.It adjusts the current value based on the minimum value and stores it as
realVal
.The frequency count of
realVal
is incremented inallCounters
.If the index of the next element with the same frequency is 0, it means this is a new frequency. In that case,
diffCount
is incremented, and the index is updated.
- Creating an array of frequency-value pairs:
- An array
allPairs
is created to store the frequency-value pairs for the unique frequencies encountered.
- Populating the
allPairs
array:
This loop iterates until
diffCount
becomes 0.The original value is calculated by adding
min - 1
to the adjusted value.Frequency and value are stored in
allPairs
, and the next index is updated.
Sorting the pairs by frequency: The
allPairs
array is sorted in descending order based on frequency.Extracting the top K frequent elements:
An array
res
is created to store the final result.The loop extracts the top K elements from
allPairs
and stores their values inres
.
- Returning the result: The function returns the
res
array containing the top K frequent elements in descending order of frequency.
This code implements a more complex algorithm to solve the problem of finding the top K most frequent elements by managing indices and frequencies directly.
Answer-3 Top Memory in Golang
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
type Pair struct {
fr int
sc int
}
func topKFrequent(nums []int, k int) []int {
mn, mx := nums[0], nums[0]
for _, v := range nums {
mn = min(mn, v)
mx = max(mx, v)
}
counter := make([]Pair, mx-mn+1)
shift := mn
for _, v := range nums {
counter[v-shift].fr += 1
counter[v-shift].sc = v
}
sort.Slice(counter, func(i, j int) bool {
return counter[i].fr > counter[j].fr
})
ans := make([]int, k)
for i := 0; i < k; i++ {
ans[i] = counter[i].sc
}
return ans
}
This code defines a function topKFrequent
that takes an array of integers nums
and an integer k
as input and returns an array containing the top K most frequent elements in the input array. Let's break down the code step by step:
Function Definitions for max and min:
- Two utility functions
max
andmin
are defined. They return the maximum and minimum of two integer values, respectively.
- Two utility functions
Defining a Pair Struct:
- A custom data structure
Pair
is defined to hold two integer values,fr
(frequency) andsc
(score/value). This will be used to store frequency-score pairs.
- A custom data structure
Function
topKFrequent
:- This function calculates the top K most frequent elements in the
nums
array.
- This function calculates the top K most frequent elements in the
Finding the Minimum and Maximum Values in the Array:
The variables
mn
andmx
are initialized with the first element of thenums
array.A loop iterates through the
nums
array and updatesmn
andmx
to find the minimum and maximum values.
Creating a Counter Array:
An array named
counter
of typePair
is created to store frequency-score pairs.The variable
shift
is set tomn
. This will be used to adjust the index in thecounter
array so that the minimum value corresponds to index 0.
Populating the Counter Array:
Another loop iterates through the
nums
array.The frequency of the element
v
is incremented in thecounter
array at the indexv - shift
. The corresponding scorev
is also stored.
Sorting the Counter Array:
- The
counter
array is sorted in descending order based on frequency. Thesort.Slice
function is used with a custom comparison function that compares the frequencies of twoPair
objects.
- The
Extracting the Top K Frequent Elements:
An array
ans
is created to store the final result.A loop iterates
k
times.The score of the
i
-th element in the sortedcounter
array is assigned to thei
-th element of theans
array.
Returning the Result:
- The function returns the
ans
array containing the top K frequent elements.
- The function returns the
In summary, this code calculates the frequency of each element in the input array and stores the frequencies along with the corresponding values in a custom Pair
structure. Then, it sorts the pairs based on frequency and extracts the top K elements by copying their values into the result array. This approach optimizes memory usage and avoids creating a separate map to store frequencies.