[LeetCode] 75. Sort Colors

轉自LeetCode

Given an array with n objects colored red, white or blue, sort them 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.

Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

<Solution>

這題是要我們將只有包含 0, 1, 2 這三個數的 array 做排序

例如 nums = {0, 1, 2, 1, 1, 0}，結果要變成 nums= {0, 0, 1, 1, 1, 2}

比較挑戰的是，不能用 sort 函式，on-pass 且 constant space

想法如下(參考資料)

• 歷遍並準備兩個指針，一個是 redIdx 指向最後一個0的下一個位置，一個是 bludIdx指向第一個 2 的前一個位置，初始值 : redIdx = 0, blueIdx = nums.size()-1

• 當遇到 0 的時候，就將該位置和 redIdx對調，redIdx++

• 當遇到 2 的時候，就將該位置和 blueIdx 對調，blueIdx-- 且 index--。因為 bludIdx 是從後面往前面走，所以和它對掉，代表把還沒檢查過的數字放到前面了，所以得將 index 也減一，再做一次檢查

• 注意一點是，歷遍只檢查到 blueIdx 的位置，因為 blueIdx 之後，已經都是確定是2了

code  如下
c++

kotlin