leetcode75: Sort Colors

题目

Given an array with n objects colored red, white or blue, sort them in-place 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.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

主要思想:

只遍历一次的就可以实现三种颜色顺序排序。利用当前元素的值,如果当前元素值等于0,则和前面标记非零元素交换,如果当前的值等于2,则和后面的值进行交换。代码如下(one pass):

class Solution {
  public void sortColors(int[] nums) {
    // 1-pass
    int p1 = 0, p2 = nums.length - 1, index = 0;
    while (index <= p2) {
        if (nums[index] == 0) {
            nums[index] = nums[p1];
            nums[p1] = 0;
            p1++;
        }
        if (nums[index] == 2) {
            nums[index] = nums[p2];
            nums[p2] = 2;
            p2--;
            index--;
        }
        index ++;
    }
  }
}

还有另外一种解法,就是遍历两边,主要思想就是统计每一种颜色出现了多少次。

说点什么

avatar
  Subscribe  
提醒

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部