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.
問題描述： 給定一個數組，數組里的每個元素代表一種顏色，紅色用0表色，白色用1表示，藍色用2表示，對數組進行一定的操作，使得數組中的0，1和2按順序排列，即前面的都是0，然后到1，最后到2。
解題思路： 看到這個題目，一開始很容易就想到對數組中的元素進行排序不就行咯？確實進行排序后是可以得到正確的結果，但是是否有這樣的必要呢？畢竟排序的復雜度不低。而且題目中已經給出了注意事項，不要用排序的方法來解決這個問題。所以，可不可以通過元素之間的交換來解決得到結果。 先從一個簡單的問題開始，從左往右遍歷數組nums，遍歷到第i元素，假如數組的前i個元素已經符合了題目的要求，那么我們應該怎樣將第i個元素插入到前面的i個元素中，使得數組前i+1個元素滿足題目的要求，如下圖。 
可以看到，當nums[i]為0的時候，經過2個步驟的交換，就可以讓前i個元素滿足題目的要求，當nums[i]為1的時候，只需要經過1個步驟的交換，就可以滿足要求，而且很容易想到，當nums[i]為2的時候，不需要任何的操作。這樣，當我們每遍歷完一個元素，都可以保證遍歷過的元素都是符合題目要求的，直到遍歷到最后一個元素。在使用這種方法的時候，關鍵點就是要記錄當遍歷到第i個元素的時候，前i個元素中第一個1的位置，和第一個2的位置，假如分別命名為start1和start2。
當遍歷到一個值為0的元素之后，經過2步交換后，需要把start1和start2都往后移動一位；當遍歷到一個值為1的元素之后，經過1步交換后，需要把start2往后移動一位；當遍歷到一個值為2的元素之后，不需要交換，也不需要改變start1和start2；而因為這些start1和start2都是初始化為0，如果給出的數組中不存在1，那么start1和start2是永遠都是想等的，那么就存在了一個問題，那就是遇到上圖中nums[i]為1這種情況的時候，會發現經過2次交換后，數組的元素順序是沒有變化的，所以如果遇到nums[i]為1的情況，只需要執行一次的交換，因為start1和start2是一樣的，所以不管是執行了第一個交換還是第二個交換，都是可行的。
代碼：
#include <iostream>#include <vector>using namespace std;void swap(vector<int>& nums, int x, int y) { int temp = nums[y]; nums[y] = nums[x]; nums[x] = temp;}void PrintNums(vector<int>& nums) { cout << "[ "; vector<int>::iterator it = nums.begin(); for (; it != nums.end(); it++) { cout << *it << " "; } cout << "]" << endl;}class Solution {public: void sortColors(vector<int>& nums) { int start0 = 0, start1 = 0, start2 = 0; int i = 0; while (i < nums.size()) { switch (nums[i]) { case 0: if (i >= start1) { swap(nums, i, start1); if (start1 != start2) swap(nums, i, start2); start1++; start2++; } break; case 1: if (i >= start2) { swap(nums, i, start2); start2++; } break; } i++; } }};int main(int argc, char** argv) { int array[] = {0, 1, 2, 1, 1}; int count = sizeof(array) / sizeof(int); vector<int> nums(array, array + count); Solution sln; sln.sortColors(nums); PrintNums(nums); return 0;}新聞熱點
疑難解答
