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.

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代码

第一种

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;
                }
            }
        }
    }
}

第二种

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代码

第一种

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

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;