Leetcode 75 Sort Colors
1. Leetcode 75 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]
2. 分析思路1
通过第一次遍历记录0、1、2对应的个数（桶排序），然后第二次遍历将0、1、2进行填入即可。
2.1 代码实现
2.1.1 C++版本
class Solution {
public:
void sortColors(vector<int>& nums) {
int a[3] = {0}; //统计0 1 2出现的次数
for (int i=0; i<nums.size(); ++i) {
++a[nums[i]];
}
int base = 0;
int digit = 0;
#外层循环表示的是几个数
for (int i=0; i<3; ++i) {
int offset = 0;
for (int j=0; j<a[i]; ++j) {
nums[base + offset] = digit;
++offset;
}
base += offset;
++digit;
}
}
};
2.1.2 Java版本
class Solution {
public void sortColors(int[] nums) {
int[] a = new int[3];
for(int i=0; i<nums.length; ++i) {
++a[nums[i]];
}
int base = 0;
int digit = 0;
for(int i=0; i<3; ++i) {
int offset = 0;
for (int j=0; j<a[i]; ++j) {
nums[base + offset] = digit;
++offset;
}
base += offset;
++digit;
}
}
}
2.1.3 Python2版本
class Solution(object):
def sortColors(self, nums):
num_counts = [0, 0, 0]
for i in nums:
num_counts[i] += 1
base = 0
digit = 0
for i in range(0, 3):
offset = 0
for j in range(0, num_counts[i]):
nums[base + offset] = digit
offset += 1
base += offset
digit += 1
3. 分析思路2
参考链接为https://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/
思路类似于三路快排，把数组arr[0, N-1] 划分为四个区间，如下所示：
- a[0, i-1] zeroes
- a[i, k-1] ones
- a[k, j] unknown
- a[j+1, len(a)-1] twos
初始值时，i=0，j=len(a)-1，而k=0，所以zeros、ones、twos三个区间均为空值。最终要使得a[k, j]区间为空，而k > j 时区间为空，所以循环的满足条件为k <= j。
3.1 代码实现
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
low = 0
mid = 0
high = len(nums) - 1
# low <= mid <= high
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[high], nums[mid] = nums[mid], nums[high]
high -= 1
class Solution {
public:
void sortColors(vector<int>& nums) {
int i = -1;
int j = 0;
int k = nums.size();
while (j < k){
if (nums[j] == 1) {
++j;
} else if (nums[j] == 0) {
swap(nums[++i], nums[j++]);
} else{
swap(nums[j], nums[--k]);
}
}
}
};
文章来源: blog.csdn.net，作者：herosunly，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/herosunly/article/details/86650961
- 点赞
- 收藏
- 关注作者
评论（0）