一个最多由0,1,2三种元素组成的无序整数数组[0,1,1,1,2,2,0,0…….],要将其按从小到大排序,时间复杂度为0(n)。
//多指针 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> sort(vector<int>& array) { // write code here int i=0, p0=0, p2=array.size()-1; while(i<=p2){ while(array[p0]==0) p0++; if(i<p0)i=p0; while(array[p2]==2) p2--; if(i>p2) break; if(array[i]==0){ swap(array[i],array[p0]); p0++; }else if(array[i]==2){ swap(array[i],array[p2]); p2--; }else if(array[i]==1){ i++; } } return array; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param array int整型一维数组 * @return int整型一维数组 */ public int[] sort (int[] array) { // write code here int[] arr = new int[array.length]; int index1 = 0; int index2 = array.length - 1; for (int i = 0; i < array.length; i++) { arr[i] = 1; } for (int i = 0; i < array.length; i++) { if (array[i] == 0) { arr[index1++] = 0; }else if (array[i] == 2) { arr[index2--] = 2; } } return arr; } }新建一个结果数组,里面全部填充1。遍历原数组,如果是0放结果数组左边,是2放结果数组右边。