在Erlang中从列表中删除重复元素

Question

我该如何在Erlang中删除列表中的重复元素？

假设我有一个类似于以下列表：

[1,1,2,3,4,5,5,6]

我该如何获得：

[1,2,3,4,5,6]

- Sina

---

输入列表已经排序了吗？ - Ed'ka

顺序很重要吗？我能重新排列这些元素吗？ - I GIVE CRAP ANSWERS

Answer 1

你可以使用集合，例如：

my_nonDuplicate_list1() ->
    List = [1,1,2,3,4,5,5,6],
    Set = sets:from_list(List),
    sets:to_list(Set).

这将返回[1,2,3,4,5]，没有重复项，但很可能未排序。

另一种不使用sets的可能性是:

my_nonDuplicate_list2() ->
    List = [1,1,2,3,4,5,5,6],
    lists:usort(List).

在这种情况下，它会返回[1,2,3,4,5]，没有重复项并且已排序。

- paper_knight

---

这个程序底层效率如何？我认为usort的时间复杂度为N log N，那么集合的时间复杂度呢？我想从列表转换到集合的时间复杂度是线性的，反之亦然，因此第一种选择可能更有效（如果不需要排序）。 - Tommy

Answer 2

对于那些希望保留列表顺序的人：

remove_dups([])    -> [];
remove_dups([H|T]) -> [H | [X || X <- remove_dups(T), X /= H]].

- expelledboy

---

这应该是被接受的答案，想要一个用于列表的 distinct 或 remove_dups 函数的要点是为了保留顺序，否则使用集合或有序集合始终是一种选择。 - Nader Ghanbari

Answer 3

一个可能的解决方案，将保留元素的顺序来帮助您学习如何操作列表，需要两个函数：

delete_all(Item, [Item | Rest_of_list]) ->
    delete_all(Item, Rest_of_list);
delete_all(Item, [Another_item| Rest_of_list]) ->
    [Another_item | delete_all(Item, Rest_of_list)];
delete_all(_, []) -> [].
remove_duplicates(List)-> removing(List,[]). 
removing([],This) -> lists:reverse(This);
removing([A|Tail],Acc) -> 
    removing(delete_all(A,Tail),[A|Acc]).

测试：

Eshell V5.9  (abort with ^G)
1> mymod:remove_duplicates([1,2,3,1,2,4,1,2,1]).
[1,2,3,4]
2>

- Muzaaya Joshua

Answer 4

模块sets有两个函数可以组合使用，以高效的方式完成工作：sets:from_list/1返回一个包含列表中所有元素的集合（根据定义不包含重复元素），sets:to_list/1返回一个包含集合元素的列表。以下是使用示例：

4> sets:to_list(sets:from_list([1,1,2,3,4,5,5,6])).
[3,6,2,5,1,4]

我们可以将该函数定义为：

nub(L) -> sets:to_list(sets:from_list(L)).

- aherranz

---

请在您的回答中添加澄清。 - Anirudh Sharma

Answer 5

依我之见，最好的选择是使用 lists:usort()。

但如果您不想使用 BIF ，且希望对列表进行排序，我建议使用快速排序的一种版本，在此实现中，您将获得已排序的列表，且不包含重复值。

unique_sort([]) -> [];
unique_sort([Pivot|T]) ->
unique_sort ([X || X <- T, X < Pivot ) ]++
[Pivot] ++
unique_sort ([X || X <- T, X > Pivot ]).

- Matt. Stroh

Answer 6

我会首先这样做来保持顺序，尽管不建议这样做。请记住，AddedStuff ++ Accumulator是可以的，但Accumulator ++ AddedStuff真的很糟糕。

rm_dup(List) ->
    lists:foldl(
        fun(Elem, Acc) ->
            case lists:member(Elem, Acc) of
                true ->
                    Acc;
                false ->
                    Acc ++ [Elem]
            end
        end, [], List
    ).

如果您想保留顺序，这个解决方案更加高效：

rm_dup(List) ->
    lists:reverse(lists:foldl(
        fun(Elem, Acc) ->
            case lists:member(Elem, Acc) of
                true ->
                    Acc;
                false ->
                    [Elem] ++ Acc
            end
        end, [], List
    )).

- Tobias Johansson