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

原创
2016/07/31 16:00
阅读数 2.8K

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/

Haskell 解法,leetcode不提供Haskell语言。

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

先sort,然后 group 分组,然后根据数量倒叙排列 sortBy (comparing (Down . length)) 然后取前 k 个,如果原数组是 [1,1,2,2,3,3] 取 k=2 则,输出[1,2] [1,3] [2,3] 等都算正确。所以这样的解法算是最精简、最简单的解法。

唯一的问题是:因为排序可能会打乱原先的顺序,所以另外一种解法是,自己写一个sort函数来实现对数组的同类合并排序,即 [2,1,2,3,2,3,1,3,1] 排序后 变成:[2,2,2,1,1,1,3,3,3] 将后面相同的提到最前面一个相同值的后面,这样原先的顺序并不会被破坏,即保留原有顺序。

利用 filter 来实现:

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

耗时120ms 或者用 each_with_object 替代reduce

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

解法的原理,nums.sort_by{|e| nums.index(e) } 类似于Haskell的 equalsort 函数,将相等的值排序到一起,不相等的保持原来顺序不变,slice_when为ruby2.2新增方法,将一个数组分隔成很多小数组,类似Haskell的group函数,将相等的归到一个数组,然后按照长度倒序排列,最后取前k个元素,最后map获取第一个。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部