leetcode75. Sort Colors

weizx 发布于2019-08-15 10:41 / 2003人阅读

摘要：将数组中的数字排序，尽量实现时间复杂度。然后在第二次遍历数组的过程中，将相应次数的，，依序填入数组中。我们要确保左指针之前的数值全部是，右指针之后的数值全部是。这样他就可以确保左右指针之间的数字为，从而实现，，的排序。

题目要求

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.
    
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?

假设一个数组中存在3个数字0，1，2。将数组中的数字排序，尽量实现O(n)时间复杂度。

思路一：O(2n)

就如题中所言，先遍历一遍数组，分别记录0，1，2出现的次数。然后在第二次遍历数组的过程中，将相应次数的0，1，2依序填入数组中。代码如下：

public void sortColors1(int[] nums) {
        int numOfZero = 0;
        int numOfOne = 0;
        for(int i = 0 ; i < nums.length ; i++){
            if(nums[i]==0){
                numOfZero++;
            }else if(nums[i]==1){
                numOfOne++;
            }
        }
        for(int i = 0 ; i0){
                nums[i] = 0;
                numOfZero--;
            }else if(numOfOne>0){
                nums[i] = 1;
                numOfOne--;
            }else{
                nums[i] = 2;
            }
        }
    }

思路二：双指针

如何能在一次遍历的过程中实现三个数字的排序呢~这就需要使用到双指针。我们要确保左指针之前的数值全部是0，右指针之后的数值全部是2。这样他就可以确保左右指针之间的数字为1，从而实现0，1，2的排序。代码如下：

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    //保证i前全是0，j后全是2，然后通过交换使得i和j中间确定为1,O(n)
    public void sortColors2(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        int ptr = 0;
        while (ptr <= j) {
            if (nums[ptr] == 0) {
                swap(nums, i++, ptr++);
            } else if (nums[ptr] == 1) {
                ptr++;
            } else {
                swap(nums, ptr, j--);
            }
        }
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU服务器私有云 Colors Leetcod LeetCode 75cdn

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

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

75. Sort Colors

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

_ivan 2019-08-16 10:30 评论0 收藏0
[Leetcode] Sort Colors 颜色排序

摘要：当遇到时，将其和序列前面一个数交换，然后将序列的指针向前移。这样，当我们遍历到序列开头时，实际上我们已经排好序了，因为所有都被交换到了前面，所有都被交换到了后面。 Sort Colors Given an array with n objects colored red, white or blue, sort them so that objects of the same col...

muddyway 2019-08-14 12:32 评论0 收藏0
75. 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...

longmon 2019-08-14 14:09 评论0 收藏0
[LeetCode] 785. Is Graph Bipartite?

Problem Given an undirected graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B such that every ed...

godlong_X 2019-08-16 13:46 评论0 收藏0
JS基础篇--JS数组常用方法汇总

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

techstay 2019-08-19 17:18 评论0 收藏0