这周一道算法题(五十七)

题目:我把题目简化下，给你一个数组，里面都是由0，1，2三个数组成，让你对这个数组进行排序。注：1、直接更改这个数组；2、不能使用代码库中的排序函数来解决这道题eg：输入: [2,0,2,1,1,0]输出: [0,0,1,1,2,2]

思路：我的思路是遍历两次，第一次记录0和1的个数，第二次更改，直接看代码：

class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        count_0 = 0 # 0的个数
        count_1 = 0 # 1的个数
        #统计个数
        for i in nums:
            if i == 0:count_0+=1
            elif i == 1:count_1+=1
        num = len(nums)
        #重写数组
        for i in range(num):
            if i < count_0:nums[i] = 0
            elif i-count_0 < count_1:nums[i] = 1
            else:nums[i] = 2

效率还不错。然后换个思路更改成只遍历一次，思路的核心就是遇到0就放到前面，遇到2就放到后面，遇到1时不变，下面是代码：

class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        #0的位置（放到前面从0开始）
        zero = 0
        #2的位置（放到后面，从最后一个开始）
        two = len(nums)
        i = 0
        #只遍历一次
        while(i < two):
            #遇到0放到前面
            if nums[i] == 0:
                nums[i], nums[zero] = nums[zero], nums[i]
                zero += 1
            #遇到2放到后面
            elif nums[i] == 2:
                two -= 1
                nums[i], nums[two] = nums[two], nums[i]
                i -= 1
            i += 1

效率差不太多，可能是实验数据的问题吧，下面再来一个别人写的，目前是效率最快的代码：

class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # 记录0和2的数量，将数组内所有元素改为1
        num0, num2 = 0, 0
        for i,n in enumerate(nums):
            if n == 0:
                num0 += 1
            if n == 2: 
                num2 += 1
            nums[i] = 1
        # 如有原数组内有0，将数组的前num0个数*0
        if num0:
            nums[:num0] = [0] * num0
        # 如有原数组内有2，将数组的后num2个数*2
        if num2:
            nums[-num2:] = [2] * num2

还有很多种方法来实现，学无止境。。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!