0%

June Leetcoding Challenge(6.11)

LeetCode六月挑战(6.11) Sort Color

Solution
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.

1
2
3
4
Example:

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

思路

(一)直接排序法
直接排序法,由于需要直接在原数组上,首先找到整个数组中最小的数,然后将他放在第一个,然后再找后面未排好数组中最小的数,放在未排序数组的第一位,以此类推。

(二) 设置三个指针,p0指向0的最右边,p2指向2的最左边,p1指向当前位置,如果p1指向的是0和p0交换,然后将p0和p1向右移动,如果p1指向的是2和p2交换,p1向右移动,p2向左移动,是1则继续。

代码

Java代码

第一种

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public void sortColors(int[] nums) {
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]>nums[j]){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
}
}

第二种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public void sortColors(int[] nums) {
int p2 = nums.length-1;
int p1=0;
int p0=0;
while (p1<=p2){
if (nums[p1] == 0){
int tmp = nums[p0];
nums[p0] = nums[p1];
nums[p1] = tmp;
p0++;
p1++;
}else if(nums[p1] == 2){
int tmp = nums[p2];
nums[p2] = nums[p1];
nums[p1] = tmp;
p2--;
}else{
p1++;
}
}
}
}

Python代码

第一种

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums);
for i in range (-1,n):
for j in range (i+1, n):
if(nums[i]>nums[j]):
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
p2 = len(nums)-1;
p1=0;
p0=0;

while p1<=p2:
if nums[p1] == 0:
nums[p0] , nums[p1] = nums[p1] , nums[p0];
p1+=1;
p0+=1;
elif nums[p1] == 2:
nums[p1] , nums[p2] = nums[p2] , nums[p1];
p2-=1;
else:
p1+=1;
-------------本文结束感谢您的阅读-------------

本文标题:June Leetcoding Challenge(6.11)

文章作者:Jungle

发布时间:2020年06月11日 - 10:26

最后更新:2020年06月11日 - 10:41

原始链接:http://yoursite.com/2020/06/11/LeetCode%E5%85%AD%E6%9C%88%E6%8C%91%E6%88%9811th/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Welcome to my other publishing channels