原文 : https://github.com/kbyyd24/bl...

题目

先把题目放上：

链接：https://leetcode.com/problems...

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?

解题思路

拿到这个题目，第一个想到的就是遍历，计数，然后赋值。这个方法很容易想到，题目也给出了提示。

然而，能只用一次遍历就得到预期的数组吗？

当然可以。按照要求，就是对数组进行遍历，找到0就放到前面去，找到1就放到中间，找到2就放到后面去。有没有很眼熟？

没错，这就是一个快速排序，因为只有0，1，2这三种数，所以仅仅需要一次遍历就能完成，连赋值都变得简单了起来。

代码

public class Solution {
public void sortColors(int[] nums) {
if (nums == null || nums.length white) {
nums[j] = nums[k];
nums[k--] = blue;
} else {
j++;
}
}
}
}

关键字：leetcode, nums, white, 遍历

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！