[Leetcode] Sort Colors 颜色排序

muddyway 发布于2019-08-14 12:32 / 3220人阅读

摘要：当遇到时，将其和序列前面一个数交换，然后将序列的指针向前移。这样，当我们遍历到序列开头时，实际上我们已经排好序了，因为所有都被交换到了前面，所有都被交换到了后面。

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

交换法 复杂度

时间 O(N) 空间 O(1)

思路

我们先用两个指针，一个指向已经排好序的0的序列的后一个点，一个指向已经排好序的2的序列的前一个点。这样在一开始，两个指针是指向头和尾的，因为我们还没有开始排序。然后我们遍历数组，当遇到0时，将其和0序列后面一个数交换，然后将0序列的指针向后移。当遇到2时，将其和2序列前面一个数交换，然后将2序列的指针向前移。遇到1时，不做处理。这样，当我们遍历到2序列开头时，实际上我们已经排好序了，因为所有0都被交换到了前面，所有2都被交换到了后面。

代码

public class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int i = 0;
        while(i <= right){
            // 遇到0交换到前面
            if(nums[i] == 0){
                swap(nums, i, left);
                left++;
                // 因为左边必定有序，所以可以直接i++
                i++;
            // 遇到2交换到后面
            } else if(nums[i] == 2){
                swap(nums, i, right);
                right--;
            } else {
            // 遇到1跳过 
                i++;
            }
        }
    }
    
    private void swap(int[] nums, int i1, int i2){
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
}

云服务器 GPU云服务器 sort排序算法 Colors LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64537.html

leetcode75. Sort Colors

摘要：将数组中的数字排序，尽量实现时间复杂度。然后在第二次遍历数组的过程中，将相应次数的，，依序填入数组中。我们要确保左指针之前的数值全部是，右指针之后的数值全部是。这样他就可以确保左右指针之间的数字为，从而实现，，的排序。题目要求 Given an array with n objects colored red, white or blue, sort them so that obj...

weizx 2019-08-15 10:41 评论0 收藏0
75. Sort Colors

摘要：题目链接这题是给数组排序，数组里面只有个变量。一个方法是用类似，个桶，统计三个变量出现的个数，然后重构数组即可。还有一种方法是用，参考算法这本书上的讲解和程序 75. Sort Colors 题目链接：https://leetcode.com/problems... 这题是给数组排序，数组里面只有3个变量。一个方法是用类似bucket sort，3个桶，统计三个变量出现的个数，然后重构...

_ivan 2019-08-16 10:30 评论0 收藏0
详解数组(Array)引用类型

摘要：例如，会删除数组中的前两项。插入的项数不必与删除的项数相等。这两个方法都接收两个参数要查找的项和可选的表示查找起点位置的索引。对数组中的每一项运行给定函数，返回每次函数调用的结果组成的数组。除Object类型外,Array是最常用的类型,Array对象与其他语言相比有着自己的不同之处,首先同一数组对象的不同项可以保存不同类型的数据,其次数组对象的长短可以动态改变. showImg(...

afishhhhh 2019-08-21 10:48 评论0 收藏0
Vue+Vue-router+Vuex项目实战

摘要：实现电商网站效果展示下载代码安装依赖启动项目运行环境需求分析登录页面商品列表页网站首页购物车页实现结算商品详情页可按颜色品牌对商品进行筛选，单击选中，再次点击取消根据价格进行升序降序销量降序排列商品列表显示图片名称销量颜色单价实时显示 shopping vue + vue-router + vuex实现电商网站效果展示 showImg(https://user-gold-cdn.xi...

zlyBear 2019-08-23 16:07 评论0 收藏0
Vue+Vue-router+Vuex项目实战

摘要：实现电商网站效果展示下载代码安装依赖启动项目运行环境需求分析登录页面商品列表页网站首页购物车页实现结算商品详情页可按颜色品牌对商品进行筛选，单击选中，再次点击取消根据价格进行升序降序销量降序排列商品列表显示图片名称销量颜色单价实时显示 shopping vue + vue-router + vuex实现电商网站效果展示 showImg(https://user-gold-cdn.xi...

Chiclaim 2019-08-30 15:56 评论0 收藏0