[Leetcode][第75题][JAVA][颜色分类][双（三）指针][计数排序]

谁践踏了优雅 2022-12-12 13:45 104阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 1. 三指针 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public void sortColors(int[] nums) { 
            int n = nums.length;
            int p0 = 0, p2 = n - 1;
            for (int i = 0; i <= p2; ++i) { 
                while (i <= p2 && nums[i] == 2) { 
                    int temp = nums[i];
                    nums[i] = nums[p2];
                    nums[p2] = temp;
                    --p2;
                }
                if (nums[i] == 0) { 
                    int temp = nums[i];
                    nums[i] = nums[p0];
                    nums[p0] = temp;
                    ++p0;
                }
            }
        }
    }

public void sortColors(int[] nums) { 
           int len= nums.length;
           int low = 0 ;
           int high= len-1;
           int i=0;
           while(i<=high){ 
               if(nums[i]==0){ 
                   int tmp = nums[i];
                   nums[i] = nums[low];
                   nums[low] =tmp;
                   ++i;
                   ++low;
               }else if(nums[i]==1){ 
                   ++i;
               }else if(i<=high && nums[i]==2){ 
                   int tmp =  nums[i];
                   nums[i] = nums[high];
                   nums[high] =tmp;
                   --high;
               }
    
           }
        }

### 快排思想理解 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]

import java.util.Arrays;
    
    
    public class Solution { 
    
        public void sortColors(int[] nums) { 
            int len = nums.length;
            if (len < 2) { 
                return;
            }
    
            // all in [0, zero) = 0
            // all in [zero, i) = 1
            // all in [two, len - 1] = 2
            
            // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
            // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
            // 所以下面遍历到 0 的时候，先交换，再加
            int zero = 0;
    
            // 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
            // 所以下面遍历到 2 的时候，先减，再交换
            int two = len;
            int i = 0;
            // 当 i == two 上面的三个子区间正好覆盖了全部数组
            // 因此，循环可以继续的条件是 i < two
            while (i < two) { 
                if (nums[i] == 0) { 
                    swap(nums, i, zero);
                    zero++;
                    i++;
                } else if (nums[i] == 1) { 
                    i++;
                } else { 
                    two--;
                    swap(nums, i, two);
                }
            }
        }
    
        private void swap(int[] nums, int index1, int index2) { 
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }
    
    作者：liweiwei1419
    链接：https://leetcode-cn.com/problems/sort-colors/solution/kuai-su-pai-xu-partition-guo-cheng-she-ji-xun-huan/

###### 2. 单指针 两次循环 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public void sortColors(int[] nums) { 
            int n = nums.length;
            int ptr = 0;
            for (int i = 0; i < n; ++i) { 
                if (nums[i] == 0) { 
                    int temp = nums[i];
                    nums[i] = nums[ptr];
                    nums[ptr] = temp;
                    ++ptr;
                }
            }
            for (int i = ptr; i < n; ++i) { 
                if (nums[i] == 1) { 
                    int temp = nums[i];
                    nums[i] = nums[ptr];
                    nums[ptr] = temp;
                    ++ptr;
                }
            }
        }
    }

#### 【总结】 ####

###### 1. 双指针三指针 有序排序重要思想 ######

###### 2.循环不变量 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]

转载链接：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c0ae3c43d2bd47778bc497504babdecb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/d785bca4916c4d0cb95093abfa84ae0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/e3237bd38eaf4bc2b603eb766334023e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/d20b535ac90542a3a6379ac1012e0a93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/a1b82029c3a24509af5a62e415e3fcb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/1931de1a38514dea91f0c7eee6f5187e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/0a6b675f43df4f8c8fb01ef5d66a865e.png