題目：給定一個(gè)長(zhǎng)度為N的整型數(shù)組arr，其中有N 個(gè)互不相等的自然數(shù)1～N。請(qǐng)實(shí)現(xiàn)arr的排序，但是不要把下標(biāo)0～N-1位置上的數(shù)通過直接賦值的方式替換成1～N

要求：時(shí)間復(fù)雜度為O(N)，額外空間復(fù)雜度為O(1)

解答：

arr在調(diào)整之后應(yīng)該是下標(biāo)從0到N-1的位置上依次放著1～N，即arr[index] = index + 1

1、從左到右遍歷arr,假設(shè)當(dāng)前遍歷到i位置

2、如果arr[i] = i + 1, 說明當(dāng)前的位置不需要調(diào)整，繼續(xù)遍歷下一個(gè)位置

3、如果arr[i] = i + 1, 說明此時(shí)i 位置的數(shù)arr[i]不應(yīng)該放在i位置上，接下來繼續(xù)進(jìn)行跳的過程

def sort1(L):if L == None or len(L) < 2:return Lfor i in range(len(L)):tmp = L[i]while tmp != i+1:tt = L[tmp-1]L[tmp-1] = tmptmp = tt

?

總結(jié)

以上是生活随笔為你收集整理的自然数数组的排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。