# 找出数组中出现次数最多的前k个元素[leetcode题]

2016/07/31 16:00

Given a non-empty array of integers, return the k most frequent elements
For example, Given [1,1,1,2,2,3] and k = 2, return [1,2]. https://leetcode.com/problems/top-k-frequent-elements/

import Data.List
import Data.Ord
topKFrequent list k = map head . take k . sortBy (comparing (Down . length)) . group . sort $list main = do print$ topKFrequent  [1,1,1,2,2,3] 2


equalsort :: (Ord a) => [a] -> [a]
equalsort []       = []
equalsort (x:xs)   = filter (==x) (equalsort xs) ++ [x] ++ filter (/=x) (equalsort xs)


equalsort 将相等的排到一起，并不改变原先顺序： 测试：

main = do
print $equalsort [2,1,2,3,2,3,1,3,1]  输出：[2,2,2,1,1,1,3,3,3] 好用equalsort来替换sort，得到另外一种写法： topKFrequent2 list k = map head . take k . sortBy (comparing (Down . length)) . group . equalsort$ list
where
equalsort []       = []
equalsort (x:xs)   = filter (==x) (equalsort xs) ++ [x] ++ filter (/=x) (equalsort xs)



golang语言的解法：

package main

import (
"fmt"
"sort"
)

type Counts [][2]int

func (c Counts) Len() int {
return len(c)
}
func (c Counts) Swap(i, j int) {
c[i], c[j] = c[j], c[i]
}
func (c Counts) Less(i, j int) bool {
return c[i][1] < c[j][1]
}

func topKFrequent(nums []int, k uint) []int {
ret := []int{}           // 返回数组
tmp := make(map[int]int) // 计算数组元素出现次数
cou := Counts{}          // Counts为二维数组。
for _, v := range nums {
if _, ok := tmp[v]; ok { // 存在，次数增加
tmp[v]++
} else {
tmp[v] = 1 // 第一次
}
}
for _, v := range nums { // 创建 Counts数组
if c, ok := tmp[v]; ok {
cou = append(cou, [2]int{v, c})
delete(tmp, v)
}
}
sort.Sort(sort.Reverse(cou))
for _, v := range cou[0:k] {
ret = append(ret, v[0])
}
return ret
}

func main() {
fmt.Println(topKFrequent([]int{1, 1, 1, 2, 2, 3}, 2))
}


go语言自定义一个类型，只要该类型实现 Len、Swap、Less三个方法，就可以直接用sort.Sort调用，提交到leetcode运算完成20个测试耗时48ms，还算比较快。

Ruby的，比较慢

def top_k_frequent(nums, k)
nums.reduce({}){|acc, x|  acc[x] ? acc[x]+=1 : acc[x] =1; acc}.sort{|x,y| y[1] <=> x[1]}.take(k).map(&:first)
end


def top_k_frequent(nums, k)
nums.each_with_object({}){|e, acc| acc[e] = (acc[e] || 0) + 1 }.sort{|i, j| j[1] <=> i[1] }.take(k).map(&:first)
end


Ruby的第二种解法，更Ruby，但速度较慢762ms

def top_k_frequent(nums, k)
nums.sort_by{|e| nums.index(e) }.slice_when{|i, j| i != j }.sort_by{|e| -e.size }.take(k).map(&:first)
end


0 评论
1 收藏
0