python - 给定一个升序排序的整数数组，编写一个算法将所有重复项推到后面。ex [1,2,2,4,5,5] 变为 [1,2,4,5,2,5]

Question

我厌倦了在 python 中这样做，但我尝试的解决方案是错误的(它不适用于超过 2 个重复项)。我试图避免使用集合或内置模块，因为我想了解潜在面试问题的逻辑。帮助

array=[1,2,2,4,5,5]
sett=list(set(array))      
print(sett+[x for x in sett if array.count(x)>1 ])

Answer 1

这看起来有点暴力，但它无需使用任何导入等即可工作。

# assumes list a is in sorted order
# if not true then sort it first
a=[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6]
b = []
c = []
for elem in a:
    if b.count(elem) == 0:
        b.append(elem)
    else:
        c.append(elem)
d = b + c
print(d)

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

编辑:我又看了一遍，有一个简单的更改，可以使其及时变为 O(n^1) 而不是 O(n^2)。

# slight modification for speed
a=[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6]
b = []
c = []
for elem in a:
    if elem not in b[-1:]: # change: look at last element in b only
        b.append(elem)
    else:
        c.append(elem)
d = b + c
print(d)

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

我运行了 %timeit 来比较两者，总结如下表。

N = list length
sort_1 = first code
sort_2 = second code
results are in seconds

    N     sort_1      sort_2
  300   0.000409    0.000104
 3000   0.035600    0.001080
30000   3.540000    0.010900

结果显示 sort_1 的时间复杂度为 O(n^2)，而 sort_2 的时间复杂度为 O(n^1)，仅进行了一点点修改。