143. Sort Colors II
中文EnglishGiven an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, … k.
样例Example1
Input:
[3,2,2,1,4]
4
Output:
[1,2,2,3,4]
Example2
Input:
[2,1,1,2,2]
2
Output:
[1,1,2,2,2]
挑战A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?
注意事项
You are not suppose to use the library’s sort function for this problem.
k <= n
class Solution:"""@param colors: A list of integer@param k: An integer@return: nothing"""def sortColors2(self, colors, k):# write your code heredef rainbowsort(colors, start, end, colorFrom, colorTo):if start == end: returnif colorFrom == colorTo: return colormid = (colorTo + colorFrom) // 2left = startright = endwhile(left <= right):while(left <= right and colors[left] <= colormid):left += 1 while(left <= right and colors[right] > colormid):right -= 1 if left <= right:colors[left], colors[right] = colors[right], colors[left]left += 1 right -= 1 rainbowsort(colors, start, right, colorFrom, colormid)rainbowsort(colors, left, end, colormid+1, colorTo)if colors == None or len(colors) == 0:returnrainbowsort(colors, 0, len(colors)-1, 1, k)