数组的partition调整

[编程题]数组的partition调整

热度指数：2072 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个有序数组arr，调整arr使得这个数组的左半部分 $[1, \frac{n+1}{2}]$ 没有重复元素且升序，而不用保证右部分是否有序

例如，arr = [1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9]，调整之后arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, .....]。

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行一个整数N。表示数组长度。
接下来一行N个整数，表示数组内元素

输出描述:

输出N个整数为答案数组

示例1

输入

16
1 2 2 2 3 3 4 5 6 6 7 7 8 8 8 9

输出

1 2 3 4 5 6 7 8 9 6 2 7 2 8 8 3

示例2

输入

5
2 3 4 4 5

输出

2 3 4 5 4

备注:



本题有special judge，对于右边的部分，你可以任意输出(在保证合法的前提下)

算法知识视频讲解

Python

毓毓子最可爱

n=input()
number_list=list(input().split())
#结果
res=[]
#利用集合去取重复
s=set()
#保留重复的元素
same=[]

for i in number_list:
    if i in s:
        same.append(i)
    else:
        res.append(i)
        s.add(i)
#在尾部添加重复的元素
for k in same:
    res.append(k)
print(' '.join(res))

发表于 2021-06-17 19:59:27 回复(0)

Python

牛客640734838号

def sort_arry(n,l):
    i=0
    j=0
    while j<n and i<n-1:
        if l[j]!=l[i]:
            l[i+1],l[j]=l[j],l[i+1]
            i+=1
        j+=1
    for i in range(n):
        print(l[i],end=" ")

def main():
    n=int(input())
    l=list(map(int,input().split()))
    sort_arry(n,l)
    
if __name__=='__main__':
    main()

发表于 2021-05-27 12:24:42 回复(0)