最大两个实现哈斯克尔

Question

给定一个整数列表xs，找到两个最大值并返回 它们成对(最大的第一)。应保留最大的重复项 (包含)在输出中。不要修改原始列表。

这就是我想出的，但它并没有给出正确的答案。这是代码，第二部分是终端运行：

minInt = minBound :: Int
maxTwoHelper1 :: [Int] -> (Int, Int)
maxTwoHelper1 (x : xs) = maxTwoHelper2 minInt minInt xs
maxTwoHelper2 :: Int -> Int -> [Int] -> (Int, Int)
maxTwoHelper2 first second [] = (first, second)
maxTwoHelper2 first second (x : xs)
| x >= first = maxTwoHelper2 x second xs
| x >= second = maxTwoHelper2 first x xs
| otherwise = maxTwoHelper2 first second xs

*Main> maxTwoHelper1 [1,0,-1]
(0,-1)

Answer 1

您的maxTwoHelper1正在删除x，它应该考虑所有元素，因此：

maxTwoHelper1 :: [Int] -> (Int, Int)
maxTwoHelper1xs= maxTwoHelper2 minBound minBound xs

您的maxTwoHelper2还包含一个错误：如果x >= first，x是最大的，first是第二大的，因此：

maxTwoHelper2 :: Int -> Int -> [Int] -> (Int, Int)
maxTwoHelper2 first second [] = (first, second)
maxTwoHelper2 first second (x : xs)
| x >= first = maxTwoHelper2 x first xs  -- 🖘 first as second largest
| x >= second = maxTwoHelper2 first x xs
| otherwise = maxTwoHelper2 first second xs

Answer 2

最简单的方法是使用sortBy：

import Data.List (sortBy)
import Data.Function (on)
import Data.Ord (Down (..))
maxTwo :: (Ord a, Bounded a) => [a] -> (a, a)
maxTwo xs = case sortBy (compare `on` Down) xs of
[] -> (minBound, minBound)
[biggest] -> (biggest, minBound)
biggest : second : _ -> (biggest, second)
-- Or, if you don't mind "can't happen" errors:
maxTwo :: (Ord a, Bounded a) => [a] -> (a, a)
maxTwo xs = case sortBy (compare `on` Down) $ minBound : minBound : xs of
biggest : second : _ -> (biggest, second)
_ -> error "Impossible!"

这是有效的，因为sortBy函数使用增量排序(它恰好是一种懒惰的自下而上的合并排序，但也有一些增量版本的堆排序和快速排序可用)。只需O(n + k * log k)时间即可获得n元素排序结果的前k个元素。请参阅这些幻灯片以获取证明。因此，为任何固定k(在本例中为 2)获取k最大的元素需要O(n)时间。