第7讲. 去重与去重排序

1. 去重

去除数组 a[0~n-1]中的重复元素。有重复的元素保留1 个。 查找，发现重复则删除。

（1）保持原有顺序关系

tail = len(a)
i = 0
while i<tail-1:
    j = i + 1
    while j<tail:
        if a[i]==a[j]:
            for k in range(j+1,tail):
                a[k-1] = a[k]
            tail -= 1
        else:
            j += 1
    i+=1
print(a[:tail])

2）不保持原有顺序关系

tail = len(a)
i = 0
while i<tail-1:
    j = i + 1
    while j<tail:
        if a[i]==a[j]:
            a[j] = a[tail-1] ; tail -= 1
        else:
            j += 1
    i+=1
print(a[:tail])

2. 去重并排序

（1）用冒泡排序实现(去重并排升序)

tail = len(a)
i = 0
while i<tail:
    # [i, tail-1]
    j = tail-1
    while i<j:
        if a[j-1]>a[j]:
            a[j-1],a[j] = a[j],a[j-1]
        elif a[j-1]==a[j]:
            a[j] = a[tail-1]; tail -= 1
        j -= 1
    i += 1
print(a[:tail])

（2）用选择排序实现（去重并排升序）

方法 1：从前往后遍历攻擂手

tail = len(a)
i = 0
while i<tail-1:
    # 未定义区间[i, tail-1]
    k=i
    j = i+1
    while j<tail:
        if a[j] < a[k]:
            k=j
        elif a[j]==a[i]:
            a[j] = a[tail-1]
            if k == tail-1:
                k = j 
            tail -= 1
            j -= 1
        j += 1
    if k!=i : 
        a[i],a[k] = a[k],a[i]
        i-=1
    i +=1
print(a[:tail])

方法 2：从后往前遍历攻擂手

tail = len(a)
i = 0
while i<tail-1:
    # 未定义区间[i, tail-1]
    k=i
    j = tail-1
    while j>i:
        if a[j] < a[k]:
            k=j
        elif a[j]==a[i]:
            a[j] = a[tail-1]
            if k == tail-1:
                k = j 
            tail -= 1
        j -= 1
    if k!=i : 
        a[i],a[k] = a[k],a[i] 
        i-=1
    i+=1
print(a[:tail])

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com