Ocaml:如何删除列表中所有重复的元素？
Ocaml:如何删除列表中所有重复的元素？
提问于 2019-10-12 16:22:55
在学习Ocaml时，我看到了一个从列表中删除重复元素的代码。
let rec remove =
function
| [] -> []
| x::[] -> x::[]
| x::y::tl ->
if x=y then remove (y::tl)
else x::remove (y::tl)但是，我发现这段代码只删除连续的重复项，所以如果我尝试一些单独的重复项，例如6;6;8;9;4;2;5;1;5;2;3，代码处理的是具有连续重复项的6，而不是分隔的2或5。
我如何才能完全使列表只有唯一的元素？如移除6;6;8;9;4;2;5;1;5;2;3 -> 6;8;9;4;2;5;1;3。
附注：我设法删除了首先出现的重复项，但不知道如何删除随后出现的重复项。
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-10-12 17:24:52
根据您的描述，您编写了算法的二次版本。还有一个O(n log n)版本，使用一组已见过的值：
let remove_duplicates (type a) (l: a list) =
let module S = Set.Make(struct type t = a let compare = compare end) in
let rec remove acc seen_set = function
| [] -> List.rev acc
| a :: rest when S.mem a seen_set -> remove acc seen_set rest
| a :: rest -> remove (a::acc) (S.add a seen_set) rest in
remove [] S.empty l(上面的代码使用了多态比较，您可能希望在真实代码中提供比较函数参数)
Stack Overflow用户
发布于 2019-10-12 16:39:43
我终于想通了。在没有排序的情况下，我做了一个元素检查和元素移除函数，这样我就可以检查列表的尾部是否有头部的重复项，并决定在删除尾部中的重复项后追加头部和尾部。将main函数作为递归函数，最终在不更改顺序的情况下删除所有重复项(并保留第一个重复项)。谢谢，glennsl。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58352265
复制相关文章
相似问题
腾讯云开发者
