LeetCode 0075 - Sort Colors
# Hints
思维 + 双指针扫描
思维 + 快速排序
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an array with 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 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]
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 a one-pass algorithm using only constant space?
# 题意
给定一个长为 的数组,且 ,要求将该数组排序,要求在一次遍历内解决问题。
# 题解
两次遍历且不限制空间的方法很简单,开个桶对 分别计数即可。
不难想到将 尽量往左边放、将 尽量往右边放。事实上,这可以用类似于快速排序的思想解决。我们维护两个指针 和 ,保证 内均为 、 内均为 。尝试后可以发现仅仅这样是不够的,我们还需要一个指针 ,令 从左往右扫,保证 内均为 ,这样就能解决问题。
该方法的技巧性较强,建议自己画一画加强理解。
细节问题:
- 注意特判空数组的情况,或在初始化时注意令
right = (int)nums.size() - 1
而不是令right = nums.size() - 1
。
# AC代码
class Solution {
public:
void sortColors(vector<int> & nums) {
// 主循环
int left = 0, right = (int)nums.size() - 1;
int index = 0;
while (index <= right) {
if (nums[index] == 0) {
swap(nums[index], nums[left]);
left ++;
index ++;
} else if (nums[index] == 1) {
index ++;
} else {
swap(nums[index], nums[right]);
right --;
}
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01