自然数数组的排序

[编程题]自然数数组的排序

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

给定一个长度为N的整形数组arr，其中有N个互不相等的自然数1-N。请实现arr的排序，但是不要把下标 $0 \sim N-1$ 位置上的数通过直接赋值的方式替换成 $1 \sim N$

[要求]

时间复杂度为

，空间复杂度为

备注：

$1\le N \le 10^5$

输入描述:

第一行有一个整数N。表示数组长度
接下来一行有N个互不相等的自然数1-N。

输出描述:

输出N个整数表示排序后的结果

示例1

输入

5
2 1 4 5 3

输出

1 2 3 4 5

备注:

算法知识视频讲解

Python

圣诞节的安徒生

N = eval(input())
ls = list(map(int, input().split()))
ls.sort()
print(' '.join(map(str, ls)))

修改了代码，尝试不用系统函数，却报如下错（连正确通过的代码都报一样的错了）

自测结果

不通过

格式错误:您的程序输出的格式不符合要求（比如空格和换行与要求不一致）
你的输出为:1 2 3 4 5

N = eval(input())
ls = list(map(int, input().split()))
for i in range(N):
    if ls[i] == i+1: # 若位置i上的值为i+1,则位置正确
        continue
    else: # 若位置i上的值不正确时
        i_index = ls.index(i+1) #先确定i+1 的正确位置
        # 将值为i+1的位置与位置i互换
        ls[i], ls[i_index] = ls[i_index], ls[i]
print(' '.join(map(str, ls)))

编辑于 2019-08-13 16:11:49 回复(1)