75. Sort Colors

longmon 发布于2019-08-14 14:09 / 1073人阅读

摘要：题目解题可以参考的这题比较简单，就没有用书里的解法，的思想就是交换，既然只能，那就一次至少搞定一个数啦解法解法只要是遇到或者，就需要采取行动

题目：
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.

Note:
You are not suppose to use the library"s sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0"s, 1"s, and 2"s, then overwrite array with total number of 0"s, then 1"s and followed by 2"s.

Could you come up with an one-pass algorithm using only constant space?

解题：
可以参考EPI的14.8, 这题比较简单，就没有用书里的解法，follow up的思想就是交换，既然只能one pass，那就一次至少搞定一个数啦
解法1:

public void Color(int[] nums, int color, int start, int len) {
        for (int i = start; i < start + len; i++) {
            nums[i] = color;
        }
    }
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        
        Map map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        
        int r = map.get(0) != null ? map.get(0) : 0;
        int w = map.get(1) != null ? map.get(1) : 0;
        int b = map.get(2) != null ? map.get(2) : 0;
        
        Color(nums, 0, 0, r);
        Color(nums, 1, r, w);
        Color(nums, 2, r + w, b);
    }

Follow up解法：

public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        
        int r = 0, b = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
        //只要是遇到0或者2，就需要采取行动
            while (nums[i] == 0 && i >= r || (nums[i] == 2 && i <= b)) {
                if (nums[i] == 0) {
                    swap(nums, i, r++);
                } else {
                    swap(nums, i, b--);
                }
            }
        }
    }

服务器托管私有云 Colors 75cdn iis75优化 75招学会数据分析

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

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

75. Sort Colors

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

_ivan 2019-08-16 10:30 评论0 收藏0
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
JS基础篇--JS数组常用方法汇总

摘要：在，下，数据有添加成功，但返回值却是转换方法方法方法用于把数组中的所有元素放入一个字符串。元素是通过指定的分隔符进行分隔的。而调用数组的方法后，其值的顺序变成了。返回值如果从中删除了元素，则返回的是含有被删除的元素的数组。转换方法所有对象都具有toLocaleString()、toString()、valueOf()方法。其中调用数组的toString方法会返回以数组中的每个值的字...

techstay 2019-08-19 17:18 评论0 收藏0
详解数组(Array)引用类型

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

afishhhhh 2019-08-21 10:48 评论0 收藏0
javascript之Array类型-读书笔记

摘要：每当在末尾添加一项后，其都会自动更新以反应这一变化。从而存在两个以上不同版本的构造函数。如果数组中的某一项值是或，那么该值在和方法返回的结果中以空字符串表示。对数组每一项运行给定函数，返回每次函数调用的结果组成的数组。 Array类型 ECMAscrip与其他多数语言中数组的共同点：都是数据的有序列表不同点：数组的每一项可以保存任何类型的数据，数组的大小是可以动态调整的，及随着数据...

kun_jian 2019-08-20 15:49 评论0 收藏0