75. 颜色分类(三指针移动||计数排序)

75. 颜色分类

75. 颜色分类(三指针移动||计数排序)

 

 

  •  根据题意提示,用计数排序扫描每个颜色的个数,然后重新往数组里填充012的个数即可,一趟扫描

class Solution {
public:
    void sortColors(vector<int>& nums) {
        map<int,int>mp;
        for(int i=0;i<nums.size();i++)
            mp[nums[i]]++;
        for(int i=0;i<mp[0];i++)
            nums[i]=0;
        for(int i=mp[0];i<mp[0]+mp[1];i++)
            nums[i]=1;
        for(int i=mp[0]+mp[1];i<nums.size();i++)
            nums[i]=2;
    }
};
  • 利用三指针,移动指针来交换数组的元素,L表示中间1区间最左边的位置,R代表中间1区间最右边的位置,表示当前的位置。遇到0就拿当前位置和L位置的元素交换,使得0到左边去,同时L++,因为此时1区间的最右边向左移动一个;遇到1就移动i,使得i++;遇到2就移动i位置和R位置的元素,使得2到右边去,同时R--,因为此时1区间的最右边向左移动一个。

    class Solution {
    public:
        void sortColors(vector<int>& nums) {
           int l=0,r=nums.size();
           int i=0;
           while(i<r)
           {
               if(nums[i]==0)
                {
                    swap(nums[i],nums[l]);l++;i++;
                }
                else if(nums[i]==1)
                {
                    i++;
                }
                else
                {
                    r--;swap(nums[i],nums[r]);
                }
           }
        }
    };

     

75. 颜色分类(三指针移动||计数排序)

上一篇:Android 4.4 Kitkat Phone工作流程浅析(四)__RILJ工作流程简析


下一篇:ESP8266 WIFI模块、Android手机有人网络调试助手(或Android手机网络调试助手)与PC端串口调试助手之间的通信