題目：

　　給定一個有序數(shù)組arr，調(diào)整arr使得這個數(shù)組的左邊部分沒有重復元素且升序，而不用保證右半部分是否有序。?
　　例如，arr = [1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9]，調(diào)整之后arr = [1, 2, 3, 4, 5, 6, 7, 8, 9……]

補充題目：

　　給定一個數(shù)組arr，其中只可能含有0,1,2三個值，請實現(xiàn)arr的排序。?
　　另一種問法：有一個數(shù)組，其中只有紅球、藍球和黃球，請實現(xiàn)紅球全放在數(shù)組的左邊，藍球放在中間，黃球放在右邊。?
　　另一種問法：有一個數(shù)組，再給定一個值k，請實現(xiàn)比k小的數(shù)都放在數(shù)組的左邊，等于k的數(shù)都放在數(shù)組的中間，比k大的數(shù)都放在數(shù)組的右邊。

基本思路：

　　原問題。該數(shù)組是有序的，只要將重復的元素放置在數(shù)組后部分即可。變量left表示數(shù)組中無重復且升序的區(qū)域范圍。初始是為0，表示區(qū)域arr[0…0]。從位置1開始遍歷數(shù)組，如果arr[i] != arr[left]，說明該元素可以加到左區(qū)域，這時候將左區(qū)域擴大一個單位用來放置arr[i]，將arr[left]和arr[i]交換并令left+1即可；如果arr[i] == arr[left]，說明該元素之前已經(jīng)出現(xiàn)過，不需要加入到左區(qū)域。

補充問題。變量left和right分別表示左右兩個區(qū)域，arr[0…left]表示都為0的區(qū)域，arr[right…N-1]表示都為2的區(qū)域。初始時令left = -1，right = len(arr)，表示區(qū)域中無任何元素。令index = 0，使用這個變量做從左到右的遍歷，arr[left+1…index]表示都為1的區(qū)域。

如果arr[index] == 0，將左區(qū)域擴大一個單位來放置該元素，把arr[left+1]和arr[index]交換即可。同時令left、index加1，繼續(xù)遍歷下一個位置。

如果arr[index] == 2，將右區(qū)域擴大一個單位來放置該元素，把arr[index]和arr[right-1]交換即可，令right減1，同時，index位置的值被更新，繼續(xù)從該位置遍歷。

如果arr[index] == 1，直接令index加1，繼續(xù)遍歷下一個位置。
?

def leftUnique(L):if L == None or len(L) < 2:return left = 0right = 1while right < len(L):if L[left] < L[right]:L[left],L[right] = L[right],L[left]left +=1right +=1else:right +=1 def sort(L,r,l,num):if L == None or len(L) < 2:returnless = l - 1more = r + 1while l < more:if L[l] < num:less +=1swap(L,l,less)l +=1elif L[l] > num:more -=1swap(L,l,more)l +=1else:l +=1def swap(L,i,j):tmp = L[i]L[i] = L[j]L[j] = tmp

?

總結

以上是生活随笔為你收集整理的数组的partition调整的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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