yoruru的努力日記

75. Sort Colors

Given an array nums 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.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

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

Example 2:

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

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

SOL：

一看到要自己寫sort有點慌張，但是看過李根逸博士的解題直播後發現也是有很簡單的做法，從bubble sort->count->two pointer的解法都有說明，超推！

【Python 與 C 的 LeetCode 六月挑戰】第十一天 (Sort Colors)

複習一下C語言指標swap的寫法：

【C 語言入門】22.1 - 兩個變數數值交換 (使用函式)

順帶一提，李根逸博士的C語言入門課程真的是講得很清楚，我是聽完之後才比較會使用指標的~

我用的是雙指標的做法，程式碼如下：

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void sortColors(int* nums, int numsSize){
    int i = 0, l = 0;
    int r = numsSize-1;
    while(i<=r){
        if(nums[i]==2){
            swap(&nums[i],&nums[r]);
            r--;
        }
        else if(nums[i]==0){
            swap(&nums[i],&nums[l]);
            l++;
            i++;
        }
        else
            i++;
    }
}