-
题目
有一个只由0,1,2三种元素构成的整数数组,请使用交换、原地排序而不是使用计数进行排序。
给定一个只含0,1,2的整数数组A及它的大小,请返回排序后的数组。保证数组大小小于等于500。
测试样例:
[0,1,1,0,2,2],6
返回:[0,0,1,1,2,2]
-
解析
class ThreeColor { public: //思路有bug vector<int> sortThreeColor(vector<int> A, int n) { // write code here int i = 0; while (A[i] == 0) i++; int k = n - 1; while (A[k] == 2) k--; int j = i; while (j < k) { if (A[j] == 0) { swap(A[i], A[j]); while (A[i] == 0) i++; } else if (A[j] == 2) { swap(A[j], A[k]); while (A[k] == 2) k--; } else { j++; } } return A; } vector<int> sortThreeColor2(vector<int> A, int n) { // write code here // 利用快排思想 int left = -1, right = n; int index = 0; while (index<right) { if (A[index]==0) { swap(A[++left],A[index]); index++; }else if (A[index]==2) { swap(A[index], A[--right]); } else { index++; } } return A; } };
- python
# -*- coding:utf-8 -*- class ThreeColor: def sortThreeColor(self, A, n): # write code here left=-1 right=n index=0 while index<right: if A[index]==0: left+=1 A[left],A[index]=A[index],A[left] index+=1 elif A[index]==2: right-=1 A[right],A[index]=A[index],A[right] else: index+=1 return A