p116 荷兰国旗问题(leetcode 75)

repinkply 2021-08-29 原文

一：解题思路

方法一：采用计数排序的思想来做，Time:O(n),Space:O(1)

方法二：只需要遍历一遍数组，Time:O(n),Space:O(1)

二：完整代码示例 (C++版和Java版)

方法一C++:

class Solution {
public:
    void sortColors(vector<int>& nums) 
    {
        if (nums.size() == 0) return;
        int count0 = 0, count1 = 0, count2 = 0;
        for (int num : nums)
        {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else count2++;
        }
        int k = 0;
        for (int i = 0; i < count0; i++) nums[k++] = 0;
        for (int i = 0; i < count1; i++) nums[k++] = 1;
        for (int i = 0; i < count2; i++) nums[k++] = 2;
    }
};

方法二C++:

class Solution {
public:
    void sortColors(vector<int>& nums) 
    {
        if (nums.size() == 0) return;
        int left = 0;
        int mid = 0;
        int right = nums.size() - 1;

        while (mid <= right)
        {
            if (nums[mid] == 0) swap(nums[left++],nums[mid++]);
            else if (nums[mid] == 1) mid++;
            else swap(nums[mid],nums[right--]);
        }
    }
};

方法一Java:

class Solution {
        public void sortColors(int[] nums)
        {
               if(nums.length==0 || nums==null) return;
               int count0=0,count1=0,count2=0;
               for(int num:nums)
               {
                   if(num==0) count0++;
                   else if(num==1) count1++;
                   else count2++;
               }
               int k=0;
               for(int i=0;i<count0;i++) nums[k++]=0;
               for(int i=0;i<count1;i++) nums[k++]=1;
               for(int i=0;i<count2;i++) nums[k++]=2;
        }
    }

方法二Java:

class Solution {
        private void swap(int[] nums,int i,int j)
        {
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }    
        
        public void sortColors(int[] nums) 
        {
               if(nums==null || nums.length==0) return;
               int left=0;
               int mid=0;
               int right=nums.length-1;
               
               while(mid<=right)
               {
                   if(nums[mid]==0) swap(nums,left++,mid++);
                   else if(nums[mid]==1) mid++;
                   else swap(nums,mid,right--);
               }
        }
    }