leetcode-75:颜色分类

简介: leetcode-75:颜色分类

题目

题目连接

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

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1:

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

示例 2:

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

解题

方法一:快排

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

方法二:将0和2分别移动到两侧

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int j=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                swap(nums[i],nums[j]);
                j++;
            }
        }
        j=nums.size()-1;
        for(int i=nums.size()-1;i>=0;i--){
            if(nums[i]==2){
                swap(nums[i],nums[j]);
                j--;
            }
        }
    }
};
相关文章
|
5天前
|
存储 算法
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
|
5天前
|
Go
golang力扣leetcode 75.颜色分类
golang力扣leetcode 75.颜色分类
27 0
|
5天前
|
Java
LeetCode-2038 如果相邻两个颜色均相同则删除当前颜色
LeetCode-2038 如果相邻两个颜色均相同则删除当前颜色
|
11月前
|
搜索推荐 Java Python
leetcode.75:颜色分类
leetcode.75:颜色分类
41 0
【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组
【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组
【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组
|
5天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0
|
5天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
12 0
|
5天前
|
算法
【刷题】 leetcode 面试题 08.05.递归乘法
递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。
25 4
【刷题】 leetcode 面试题 08.05.递归乘法