按值排序Data.Map并获取所有最大值 [英] Sort Data.Map by value and get all biggest values

问题描述

  fromList [（eso，1），（mes ，1），（ome，2），（som，2）] 
  

我需要从这张地图上的值最大的键列表中找到：

  [ome，som] 
  

以下是我的解决方案：

  get_max_from_map m = map fst（filter is_biggest sorted）
 where sort = List.sortBy（\（k1，v1）（k2，v2） - > v2`compare` v1）$ Map.toList m 
 max_v = snd $ head 
 is_biggest（key，value）= value == max_v 
  

我将map转换为list，对它们进行排序，获得第一个值作为最大值并过滤列表。

我只是想知道是否存在更优化和这个任务的美丽的解决方案？

谢谢。

解决方案

并不比原来的文章简单，但它具有线性时间的优点，一次性解决方案（您的版本是O（ n log n ），因为它对列表进行分类，到目前为止发布的其他答案都是两遍解决方案） p>

  getMaxFromMap m = go [] Nothing（Map.toList m）
 where 
 go ks _ [] = ks 
 go ks Nothing（（k，v）：rest）= go（k：ks）（Just v）rest 
 go ks（Just u）（（k，v）：rest）
 | v< u = go ks（就是你）休息
 | v> u = go [k]（Just v）休息
 |否则= go（k：ks）（Just v）rest 
  

I have Data.Map that looks like this:

fromList [("eso",1),("mes",1),("ome",2),("som",2)]

I need to get list of keys from this map where the values are biggest:

["ome","som"]

Here is my solution:

get_max_from_map m = map fst (filter is_biggest sorted)
    where sorted = List.sortBy (\(k1, v1) (k2, v2) -> v2 `compare` v1) $ Map.toList m
          max_v = snd $ head sorted
          is_biggest (key, value) = value == max_v

I convert map to list, sort them, get first value as maximum and filter list.

I am just wondering if there is more optimal and beautiful solution of this task ?

Thanks.

解决方案

This isn't any simpler than what is in your original post, but it has the advantage of being a linear-time, one-pass solution (your version is O(n log n) since it sorts the list, and the other answers posted so far are two-pass solutions).

getMaxFromMap m = go [] Nothing (Map.toList m)
  where
    go ks _        []           = ks 
    go ks Nothing  ((k,v):rest) = go (k:ks) (Just v) rest
    go ks (Just u) ((k,v):rest)
        | v < u     = go ks     (Just u) rest
        | v > u     = go [k]    (Just v) rest
        | otherwise = go (k:ks) (Just v) rest

这篇关于按值排序Data.Map并获取所有最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！