荷兰国旗算法介绍和实现方法

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

此题中，我们使用整数0、1和分别表示红色、白色和蓝色。

示例：

输入：nums=[,0,,1,1,0]输出：[0,0,1,1,,]输入：nums=[,0,1]输出：[0,1,]输入：nums=[0]输出：[0]输入：nums=[1]输出：[1]思路

经典荷兰旗算法，用双指针标记左侧和右侧的序号，一遍遍历，到右侧指针处停止遍历，等于0的与左侧交换，等于的与右侧交换，但是要注意一种特殊情况，比如和右侧交换时，被交换的数可能本身就是0或，这样会导致被交换的这个0或无法被后续遍历处理到，因此当0与本身被交换时需要回退当前遍历的序号，再处理一遍当前序号的0或。

上代码（js）

/***

param{number[]}nums*

turn{void}Donotturnanything,modifynumsin-placeinstead.*/varsortColors=function(nums){letleftIndex=0,rightIndex=nums.length-1;for(letsearchIndex=0;searchIndexrightIndex;searchIndex++){if(searchIndex===0){[nums[searchIndex],nums[leftIndex]]=[nums[leftIndex],nums[searchIndex]];leftIndex++;}if(searchIndex===){[nums[searchIndex],nums[rightIndex]]=[nums[rightIndex],nums[searchIndex]];rightIndex--;if(nums[searchIndex]===0

nums[searchIndex]===){searchIndex--;}}}};

上代码（python）

classSolution:defsortColors(self,nums:List[int])-None:"""Donotturnanything,modifynumsin-placeinstead."""leftIndex=0;rightIndex=len(nums)-1;searchIndex=0;whilesearchIndex=rightIndex:ifnums[searchIndex]==0:nums[searchIndex],nums[leftIndex]=nums[leftIndex],nums[searchIndex];leftIndex+=1;ifnums[searchIndex]==:nums[searchIndex],nums[rightIndex]=nums[rightIndex],nums[searchIndex];rightIndex-=1;ifnums[searchIndex]==0ornums[searchIndex]==:searchIndex-=1;searchIndex+=1;

转载请注明：http://www.abuoumao.com/hyfz/5953.html