LeetCode 75.颜色分类(荷兰国旗问题)

题目:

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

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

思路:

  1. 本题是典型的荷兰国旗问题,我们不能仅仅局限于当前题目,有的题目变一下就不是三个数,而是三个区域,小于num的,等于num的以及大于num的。
  2. 为了规划区域,我们可以设置两个指针left,rightleft表示左边区域的右边界,初始时指向第一个元素的前一个,索引为-1right表示右边区域的左边界,初始时指向最后一个元素的后一个,索引为nums.length,指针cur表示当前遍历的值,这样就会出现三种情况,我们假定num为目标分界值
    1. 当前值nums[cur]<num,那么当前值就是属于left区域的,让该值和left的下一位交换,然后让left++,cur++,这样就保证该值被包进了left区域
    2. 当前值nums[cur]==num,那么当前值就是中间区域的,只需要让cur++
    3. 当前值nums[cur]>num,那么当前值就是属于right区域的,我们让当前值和right区域的前一个进行交换,然后让right--,这样就保证了该值被包进了right区域注意,这个情况下指针cur不能+1,因为cur和right区域前一个值交换之后的当前值是从后边来的,还没有遍历过,所以不能记着将cur++
  3. 最后当遍历到cur指针和right指针相碰时,说明所有元素遍历完毕,整个数组也就有序了。

以下为代码+注释:

    public void sortColors(int[] nums) {
        int cur = 0;
        // 初始化时左边区域指向第一个元素的前面,
        // 右边区域指向最后一个元素的后面,两个指针都是一直在向中间扩张
        int left = -1, right = nums.length;
        // 从第一个开始遍历,直到当前遍历的值和右边的区域重合
        while(cur != right){
            // 情况一:如果当前值小于1,将nums[cur]和left区域的下一个做交换,让后让left区域向右扩一个,最后cur++
            if(nums[cur] < 1){
                int temp = nums[cur];
                nums[cur] = nums[left + 1];
                nums[left + 1] = temp;
                left++;
                cur++;       
            }else if(nums[cur] == 1){
                // 情况二:如果当前值等于1,cur++,其他什么也不干
                cur++;
            }else{
                // 情况三:如果当前值大于1,将当前值和right区域的前一个做交换,right区域向左扩,注意此情况cur指针不动,因为交换过之后当前cur指向的值是后面的right区域交换过来的,我们还没有处理过。
                int temp = nums[cur];
                nums[cur] = nums[right - 1];
                nums[right - 1] = temp;
                right--;
            }
        }
    }

笔者也在不断学习,如有错误,欢迎指正!

上一篇:Java人机猜拳游戏 (完整代码+详细注释+粘贴即食)


下一篇:机器学习sklearn(75):算法实例(三十二)回归(四)线性回归大家族(二)多元线性回归LinearRegression