Top K Frequent Elements

题目描述：

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
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.

思路:

先排序，然后算出频繁次数构建结构体，结构体的频繁次数排序，最后得出结果

代码:

type Num struct {
    n,f int
}
func topKFrequent(nums []int, k int) []int {
    res := make([]int, k)
    n := len(nums)
    sort.Ints(nums)
    var pairs []Num 
    pairs = append(pairs, Num{n:nums[0],f:1})
    for i:=1;i<n;i++{
        if nums[i] != nums[i-1]{
            pairs = append(pairs, Num{n:nums[i],f:1})
        }else{
            pairs[len(pairs)-1].f++
        }
    }
    sort.Slice(pairs,func (i,j int)bool{
        if pairs[i].f  > pairs[j].f{
            return true
        }else{
            return false
        }
    })
    for i:=0;i<k;i++{
        res[i] = pairs[i].n
    }
    return res
}

代码效率：

执行用时：12 ms, 在所有 Go 提交中击败了90.99%的用户
内存消耗：4.9 MB, 在所有 Go 提交中击败了99.82%的用户