[75] Sort Colors

增加信心用Orz
(還是其實是打擊呢哈哈 XD)
有0, 1, 2 三種顏色存在array裡
把它們依照0,1,2排列
產生 00000 11111 2222 這樣的array.
一開始還以為要產生 012012012的
沒想到不是Orz
再度想難了是嗎Orz

Sort Colors
void sortColors(int* nums, int numsSize) {
    int i,numsI=0;
    int count[3] = {0,0,0};
    for (i=0;i<numsSize;i++)
        count[nums[i]]++;

    for (i=0;i<3;i++)
        for (int k = 0; k< count[i];k++)
            nums[numsI++]= i;
}

據說是可以只跑一次,
把0都掃到左邊, 2都掃到右邊, 中間自然留下1 這樣.
唉覺得好累
今天進度超級少QQ
傷心

20221126 更新

說是有一個algorithm 叫做 Dutch national flag problem: https://en.wikipedia.org/wiki/Dutch_national_flag_problem

然後重新用這個演算法寫了一遍兒～～～

void swap(int *a, int *b)

{

int tmp;

tmp = *a;

*a=*b;

*b=tmp;

}

void sortColors(int* nums, int numsSize){

int low, mid,high;

low=0;

mid=0;

high=numsSize-1;

while (mid<=high)

{

if (nums[mid]==1)

{

mid++;

}

else if (nums[mid]==2)

{

swap(&nums[mid], &nums[high]);

high--;

}

else //nums[mid]==0

{

swap(&nums[low], &nums[mid]);

low++;

mid++;

}

}

}