首页 > 其他 > 详细

[leetcode 75] Sort Colors

时间:2015-05-20 23:49:16      阅读:226      评论:0      收藏:0      [点我收藏+]

1 题目

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.

2 思路

好吧,这题是我见过最简单的,居然是中等难度,只要之前听说过这种类型的题目,都会做。就是count sort法。

数1,2,0的个数,然后再遍历赋值就行了。

 

3 代码

public void sortColors(int[] nums) {
        int redNumber = 0;
        int whiteNumber = 0;
        for(int i = 0;i < nums.length; i++){
            if(nums[i] == 0){
                redNumber++;
            }else if(nums[i]==1){
                whiteNumber++;
            }
        }
        for(int i = 0; i < redNumber; i++){
            nums[i] = 0;
        }
        for(int i = redNumber; i < redNumber + whiteNumber; i++){
            nums[i] = 1;
        }
        for(int i = redNumber + whiteNumber; i < nums.length; i++){
            nums[i] = 2;
        }
    }

 

遍历一遍的方法:https://leetcode.com/discuss/17000/share-my-one-pass-constant-space-10-line-solution

the idea is to sweep all 0s to the left and all 2s to the right, then all 1s are left in the middle.

class Solution {
    public:
        void sortColors(int A[], int n) {
            int second=n-1, zero=0;
            for (int i=0; i<=second; i++) {
                while (A[i]==2 && i<second) swap(A[i], A[second--]);
                while (A[i]==0 && i>zero) swap(A[i], A[zero++]);
            }
        }
    };

 

[leetcode 75] Sort Colors

原文:http://www.cnblogs.com/lingtingvfengsheng/p/4518539.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!