Sort Color II

Question

Given 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.

Example Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].

Challenge 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?

Analysis

k是否会大于所有color的总数？ time, space的要求

Thoughts

sort color II

每次选两个

Solution

class Solution:
    """
    @param colors: A list of integer
    @param k: An integer
    @return: nothing
    """
    def sortColors2(self, colors, k):
        # write your code here
        count = 0
        start = 0
        end = len(colors) - 1
        remain = list(colors)
        while count < k:
            if not remain:
                break
            minColor = min(remain)
            maxColor = max(remain)
            colors, numColor1, numColor2 = self.sortColors(colors, minColor, maxColor, start, end)
            start += numColor1
            end -= numColor2
            count += 2
            remain = colors[start:end]
        return colors

    def sortColors(self, nums, color1, color2, start, end):
        # write your code here
        numRed = 0
        numBlue = 0
        index = start
        while index <= end - numBlue:
            if nums[index] == color1:
                nums = self.swap(nums, start + numRed, index)
                numRed += 1
                index += 1
            elif nums[index] == color2:
                nums = self.swap(nums, end - numBlue, index)
                numBlue += 1
            else:
                index += 1

        return nums, numRed, numBlue


    def swap(self, nums, i, j):
        tmp = nums[j]
        nums[j] = nums[i]
        nums[i] = tmp
        return nums