如何在Haskell的列表中找到第二大號碼？

編寫一個函數，該函數接受一個整數列表並返回其長度，並返回列表中第二大整數。

我可以用兩個函數解決這個問題，但有沒有解決方案只使用一個函數來完成它？

任何幫助表示讚賞！謝謝！

2013-10-01 Zip

你對「1功能」與「2功能」的定義是什麼？你可以把第二個放在第一個的where子句中，然後它只有一個函數:) – us2012

在一次通過中查找前k個項目（因此是第k個最大項目）的一般解決方案使用優先級隊列，所以在迭代的每一步中，你總是知道前k個。這裏有一篇博客文章（http://stevehanov.ca/blog/index.php?id=122）。對於非常小的k，優先級隊列在性能方面可能過於誇張，但它可能最容易遵守 - 不要過早優化IOW。我確信Haskell庫中有一個合適的優先級隊列。 – Steve314

@ Steve314我認爲這在Haskell中是不必要的，因爲懶惰評估意味着使用類似take k（sort xs）的應該是有效的。 –

編輯使用@ThomasM.DuBuisson's建議

可以解決這個問題，你可以找到最大的相同方式：採用倍。最大可以很平凡與

mymaximum :: Ord a => [a] -> a 
mymaximum xs = foldl searcher (head xs) xs 
    where 
     searcher :: Ord a => a -> a -> a 
     searcher a b 
      | a > b  = a 
      | otherwise = b

由剛剛跟上兩個最大的價值實現，從而我們可以實現它類似（請注意，我們以「種子」的倍元組以及）：

nextmaximum :: Ord a => [a] -> a 
nextmaximum xs = fst $ foldl searcher (h, h) xs 
    where 
     h = head xs 
     searcher :: (Ord a) => (a, a) -> a -> (a, a) 
     searcher (s, f) x = (min f (max s x), max f x)

來源

2013-10-01 21:55:59 bheklilr

'searcher（s，f）x =（min f（max s x），max f x）' –

@ ThomasM.DuBuisson好的建議，它會更快，更簡單。 – bheklilr

@zip注意這個解決方案是部分的 - 如果傳遞一個空列表，它將引發異常。很容易改變這種行爲（模式將參數匹配到'nextmaximum'並處理特殊情況），但不清楚你想在這種情況下做什麼。 –

您可以將各個功能組合在一起。這既不高效也不健壯，但它確實容易編寫：

f xs = maximum . filter (< maximum xs) $ xs

來源

2013-10-01 22:04:48 jtobin

不要讓它變得複雜。

f xs = (sort xs !! 1, length xs)

如果您選擇使其變得複雜，make it complicated in the right way。

來源

2013-10-02 01:05:02

我將'第二大整數'解釋爲數量級。即在'[1,1,2,3,3]'中，我們想要2.（psst，你的排序順序是向後的;））。 – jtobin

由於Daniel尚未解決這個問題 - 要改變sort排序，請使用['sortBy']（http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-List.html ·V：sortBy）。或者，根據現有代碼的精神，使用類似「反向」的內容。 $ xs排序！ 1'。或者，因爲無論如何正在評估'length xs'，請使用'sort xs !! （長度xs - 2）'。 – Steve314

head . (!!1) . group . sortBy (flip compare) $ [1,1,2,3,4,4,4,5,5,6,6,6,6] 
5

來源

2013-10-02 08:40:14 klapaucius

如何在Haskell的列表中找到第二大號碼？

回答

相關問題