maxTwo 实现 Haskell

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)
maxTwoHelper1 xs = 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  -- 

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)时间。