文档章节

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

hell0cat
 hell0cat
发布于 2016/07/31 16:00
字数 768
阅读 166
收藏 1

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获取第一个。

© 著作权归作者所有

共有 人打赏支持
hell0cat
粉丝 37
博文 48
码字总数 24082
作品 0
徐汇
程序员
私信 提问
LeetCode--Majority Element--Boyer-Moore算法总结

找数组中的Majority Element,Majority Element的定义见下,对应着LeetCode上的两道题,直接看题: LeetCode--169. Majority Element 给定一个长度为n的数组,找出其中的Majority Element。其...

CLthinking
2018/12/22
0
0
LeetCode算法题-Range Addition II(Java实现)

这是悦乐书的第271次更新,第285篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第138题(顺位题号是598)。给定一个m行n列的新二维数组M,其初始值为0。提供一个二维数组ops...

小川94
03/09
0
0
在海量数据里查询多少条数据的这类问题经常被问起,该如何回答?

1、海量日志数据,提取出某日访问百度次数最多的那个IP IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。 再详细介绍下此方案:首先是这一天,并且是...

瑞查德-Jack
01/08
0
0
十道海量数据处理面试题与十个方法大总结

海量数据处理:十道面试题与十个海量数据处理方法总结 本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。 出处:http://blog.csdn.net/vJULYv。 第一部分、十道海量数据处理面试题...

吟啸_徐行
2014/04/02
0
2
海量数据处理 - 十道面试题与十个海量数据处理方法总结

第一部分、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 或者如下阐述(雪域之鹰):算法思想:分而治之+Hash1.IP地址最多有2^32=4G种取值情况,所以不能...

小王穷遊
2018/09/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【C++】智能指针简述(四):shared_ptr

  在开始本文内容之前,我们再来总结一下,前文内容:   1.智能指针采用RAII机制,在构造对象时进行资源的初始化,析构对象时进行资源的清理及汕尾.   2.auto_ptr防止拷贝后析构释放同一块内...

shzwork
24分钟前
1
0
作为Java程序员这些技术都不会,拿什么去涨薪跳槽?

引言 当下,正面临着近几年来的最严重的互联网寒冬,听得最多的一句话便是:相见于江湖~,缩减HC、裁员不绝于耳,大家都是人心惶惶,年前如此,年后想必肯定又是一场更为惨烈的江湖厮杀。但博...

别打我会飞
47分钟前
2
0
springboot开发之定时器quartz 定时任务调度(压缩版,抽取quartz的单个任务表实现)

前言 老了, 记不住了, 好记性不如烂笔头; 没想到曾经过目不忘的我, 也有这么一天, 岁月蹉跎,学习一天不如一天 难受 Quartz可以用来做什么? Quartz是一个任务调度框架。比如你遇到这样的问题...

尾生
52分钟前
11
0
技术经理平时都干啥?

「技术主管」是开发团队中的某位程序员需要对一起创建系统的整个开发团队负责时所承担的角色。通常他既要对最终交付的软件系统负责,另外也会像一个程序员一样去开发实现系统。 一个技术主管...

春哥大魔王的博客
今天
7
0
java工作流引擎Jflow流程事件和流程节点事件设置

流程实例的引入和设置 关键词: 开源工作流引擎 Java工作流开发 .net开源工作流引擎 流程事件 工作流节点事件 应用场景: 在一些复杂的业务逻辑流程中需要在某个节点或者是流程结束后做一些业...

ccflow周朋
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部