这周一道算法题(五十七)
2018-06-25 本文已影响33人
CrazySteven
题目:我把题目简化下，给你一个数组，里面都是由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
还有很多种方法来实现，学无止境。。。。
