为何Python调用set()会将负值移至列表末尾？时间复杂度是多少？

1. 为什么set(nums)会改变元素顺序，把-1移到末尾？ #

Python的set（集合）是无序且自动去重的数据结构，它不会保留原列表的元素顺序。你看到的-1在末尾只是集合内部哈希存储的随机结果，集合的元素排列完全由元素的哈希值决定，和原列表的顺序没有任何关联。另外你注释里写的输出{1, 2, 3, 5, 7, 9, 9, 9, 11, -1}是错误的，集合会自动剔除重复元素，实际转成集合后应该是无重复的，比如{-1, 1, 2, 3, 5, 7, 9, 11}（具体显示顺序可能因Python版本或环境略有差异，但肯定是无序的）。

2. 关于用sorted(set(nums))获取有序结果 #

你用sorted(set(nums))的思路是可行的，这个操作会先通过集合去重，再把去重后的元素按升序排序，最终得到一个有序列表。如果需要保留原列表中元素第一次出现的顺序，也可以用dict.fromkeys(nums)（Python 3.7及以上版本支持），因为字典会保留插入顺序，这样既能去重又能保留原顺序：

nums[:] = list(dict.fromkeys(nums))

执行后nums会变成[-1, 2, 3, 5, 7, 9, 11, 1]，和原列表元素第一次出现的顺序一致。

3. 时间复杂度判断纠正 #

你的判断存在错误：

• set(nums)的时间复杂度是O(n)，因为遍历列表每个元素并插入集合的平均操作是O(1)。
• sorted()的时间复杂度是O(m log m)，其中m是去重后的元素数量（m ≤ n），因为Python内置的排序算法Timsort的时间复杂度为O(k log k)。
• 所以总体时间复杂度是O(n + m log m)，当原列表几乎无重复时（m接近n），总体复杂度为O(n log n)，而非你认为的O(n²)。

内容的提问来源于stack exchange，提问作者Ramen Free Finance