python每日一题练习

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

里面的要求1是要进行原地排序 2是不使用库内置的sort函数

有很多的排序方法 就比如我们可以使用冒泡排序啊 最简单的

1.

class Solution(object):def sortColors(self, nums):n = len(nums)for i in range(n - 1):swapped = Falsefor j in range(n - 1 - i):if nums[j] > nums[j + 1]:nums[j], nums[j + 1] = nums[j + 1], nums[j]swapped = Trueif not swapped:  # 无交换则已有序breakreturn nums
solution=Solution()
result=solution.sortColors([2,0,2,1,1,0])
print(result)

就这样就行了

但是肯定不是这么简单 我们来开阔一下新思路 既然是只有三个元素 0 1 2 那么是不是可以统计0 1 2 的数目 然后就前几个是0 中间几个是1 后面几个是2 

2.

class Solution(object):def sortColors(self, nums):n = len(nums)if n==0 or n==1:return numscount1=count2=count3=0for i in range(n):if nums[i]==0:count1+=1elif nums[i]==1:count2+=1else:count3+=1nums[:] = [0] * count1 + [1] * count2 + [2] * count3return nums
solution=Solution()
result=solution.sortColors([0])
print(result)

这个思路很不错 但是不是我想的 是我看评论区里面的大佬想的思路 我觉得很灵活很牛了 所以给它记录下来

然后还有什么方法呢？

是不是可以使用双指针 已经一共才三个情况 0到Left就是0 left到right就是1 right到末尾就是2 还有这样的思路 

class Solution(object):def sortColors(self, nums):n = len(nums)if n==0 or n==1:return numsleft=0right=n-1i=0while i <= right:if nums[i]==0:temp=nums[i]nums[i]=nums[left]nums[left]=templeft+=1i+=1elif nums[i]==2:nums[i]=nums[right]nums[right] = 2right-=1else:i+=1return nums
solution=Solution()
result=solution.sortColors([0,1,1,2,2,1])
print(result)

这个代码的思路就是双指针 遍历整个数组 如果是0 那么这个地方的值就要和left的位置的值进行互换 如果是2 那就需要和right处的元素进行互换 这样的话就会使得最后1就是在中间的 0 2各在两边 

这道题还蛮有意思的 希望大家可以跟我一起 学会这些思路~