leetcode.75:颜色分类

简介: leetcode.75:颜色分类

题目描述:


给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


示例:


输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]


进阶:


· 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
· 你能想出一个仅使用常数空间的一趟扫描算法吗?


题目难度:中等


分析:


简化题目,忽略颜色的干扰,可以理解为一个数组中只有0, 1, 2三个元素,然后对数组排序。我们知道数组排序算法最快的也是O ( n l o g n ) O(nlogn)O(nlogn),所以并不符合题意,当然只有3个元素也没有必要排序就是了,并且题目中也给了一个方法,此方法比较简单,不是本文的重点,不过依然会给出参考代码。


进阶:从最终结果来看,数组顺序必然是按照000111222来排列的,所以可以理解为:0元素都在最左边,1在中间,2在最右边,相同元素之间并没有顺序,所以首先应该有3个指针left, current, right,前两者在左,后者在右。然后遍历数组,遇0则left, current交换,然后两个指针同时右移,遇2则current, right交换,然后right指针左移,遇1则不交换,但是current右移即可。代码如下:


java:


class Solution {
    public void sortColors(int[] nums) {
      // 表示0, 1, 2三个元素的个数
        int zeroCount = 0, oneCount = 0, twoCount = 0;
        for (int num : nums) {
          // 判断数字,同时对应的个数加1
            switch (num) {
                case 0:
                    zeroCount++;
                    break;
                case 1:
                    oneCount++;
                    break;
                default:
                    twoCount++;
            }
        }
        // 最后分别按照3个元素的个数修改数组中的元素即可
        for (int i = 0; i < nums.length; i++) {
            if (zeroCount > 0) {
                nums[i] = 0;
                zeroCount--;
            } else if (oneCount > 0) {
                nums[i] = 1;
                oneCount--;
            } else {
                nums[i] = 2;
            }
        }
    }
}


python:


class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero_count, one_count, two_count = 0, 0, 0
        for num in nums:
            if num == 0:
                zero_count += 1
            elif num == 1:
                one_count += 1
            else:
                two_count += 1
        for i in range(len(nums)):
            if zero_count > 0:
                nums[i] = 0
                zero_count -= 1
            elif one_count > 0:
                nums[i] = 1
                one_count -= 1
            else:
                nums[i] = 2


进阶版java:

class Solution {
    public void sortColors(int[] nums) {
      // 分别定义3个指针
        int left = 0, current = 0, right = nums.length - 1;
        while (current <= right) {
            int num = nums[current];
            // 如果num = 0则交换left, current
            if (num == 0) {
                swap(nums, left, current);
                left++;
                current++;
            // 如果num = 2则交换current, right
            } else if (num == 2) {
                swap(nums, current, right);
                right--;
            // 否则为1
            } else {
                current++;
            }
        }
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}


进阶版python:


class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left, current, right = 0, 0, len(nums) - 1
        while current <= right:
            num = nums[current]
            if num == 0:
              // python语法支持这样的交换值逻辑,所以并不需要定义交换值方法
                nums[left], nums[current] = nums[current], nums[left]
                left += 1
                current += 1
            elif num == 2:
                nums[current], nums[right] = nums[right], nums[current]
                right -= 1
            else:
                current += 1


总结:


普通版时间复杂度为O(2n),进阶版时间复杂度为O(n),此题如果不考虑进阶版应该是简单难度,进阶版如果知道了方法也很好理解,就是可能不太好想到此方法,多刷题即可。

目录
相关文章
|
13天前
|
存储 算法
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
|
13天前
|
Go
golang力扣leetcode 75.颜色分类
golang力扣leetcode 75.颜色分类
28 0
|
13天前
|
Java
|
13天前
leetcode-75:颜色分类
leetcode-75:颜色分类
28 0
LeetCode-2038 如果相邻两个颜色均相同则删除当前颜色
LeetCode-2038 如果相邻两个颜色均相同则删除当前颜色
【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组
【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组
【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组
|
1天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
10 1
|
1天前
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
7 0
|
1天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
7 0
|
4天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
8 1