首页 > 代码库 > leetcode[75] sort colors
leetcode[75] sort colors
给定一个数组，有0,1,2三个数，把数组排好序。不能直接用sort。
策略一：
简单的思路，扫描两次，第一次记录0,1,2的个数，第二次重写数组。
class Solution {public: void sortColors(int A[], int n) { if(n < 2) return ; int n0 = 0, n1 = 0, n2 = 0; vector<int> ans(n); for (int j = 0; j < n; j++) { if (A[j] == 0) n0++; else if (A[j] == 1) n1++; else n2++; } int i = 0; while(i < n0) {A[i] = 0;i++;} while(i < n0 + n1) {A[i] = 1;i++;} while(i < n0 + n1 + n2) {A[i] = 2;i++;} return ; }};
但，要求只扫描一次，常数空间。
策略二：
定义一个left，一个right
1. 遇到1，left++
2. 遇到2，和right位置换
3. 遇到0，往前和第一个非零数字换，left++
class Solution {public: void sortColors(int A[], int n) { int left = 0, right = n -1; while(left <= right) { if (A[left] == 0) { int index = left - 1; while(index >= 0 && A[index] != 0) index--; // 这个算扫描一次吗？ if (index < 0) swap(A[0], A[left]); else swap(A[index+1], A[left]); left++; } else if (A[left] == 1) ++left; else if (A[left] == 2) { swap(A[left], A[right]); right--; } } }};
策略三：
借助于快速排序的partition思想，以1为枢纽元对数组进行划分，使0在数组的左边，2在数组的右边，1在数组的中间。
class Solution {public: void sortColors(int A[], int n) { //zeroEnd是放0那部分的尾部索引，twoEnd是放2那部分的首部索引 //碰到0放到zeroEnd+1处，碰到2放到twoEnd-1处，碰到1指针后移 int zeroEnd = -1, twoBegin = n, i = 0; while(i < twoBegin) { if(A[i] == 0 && i != ++zeroEnd) swap(A[zeroEnd], A[i]); else if(A[i] == 2 && i != --twoBegin) swap(A[twoBegin], A[i]); else i++; } }};
leetcode[75] sort colors
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。