【75颜色分类】

前言题目源码

前言

今天的题目就是一个排序题，试了下冒泡虽然过了，但是可想而知效率很低，哈哈哈然后想了个耍无赖的方法,方法3采用双指针。

题目

官方题目

源码

冒泡的效率可想而知

class Solution { public void sortColors(int[] nums) { int len=nums.length; // 冒泡 // for(int i=0;i<len-1;i++){ // for (int j=0;j<len-1-i;j++){ // if(nums[j]>nums[j+1]){ // int tmp=nums[j]; // nums[j]=nums[j+1]; // nums[j+1]=tmp; // } // } // } // 方法2，显然不是一个好方法，但是针对本题效率很高 // int[] colorNum=new int[3]; // for(int i=0;i<len;i++){ // colorNum[nums[i]]++; // } // for(int i=0;i<colorNum[0];i++)nums[i]=0; // for(int i=0;i<colorNum[1];i++)nums[i+colorNum[0]]=1; // for(int i=0;i<colorNum[2];i++)nums[i+colorNum[0]+colorNum[1]]=2; // 方法3，双指针 int p0=0,p1=0; for (int i=0;i<len;i++){ if(nums[i]==1){ int tmp=nums[i]; nums[i]=nums[p1]; nums[p1]=tmp; p1++; }else if(nums[i]==0){ int tmp=nums[i]; nums[i]=nums[p0]; nums[p0]=tmp; if(p0<p1){ tmp=nums[i]; nums[i]=nums[p1]; nums[p1]=tmp; } p0++; p1++; } } } }

方法2就比较耍流氓了 方法3其实无明显改善，就是少了个for