題目
5.png
給定一個(gè)數(shù)組{-1,1,0,-1,0,1} 數(shù)組中只有確定的3種重復(fù)元素-1,0,1，設(shè)計(jì)一個(gè)算法將其排列成{-1,-1,0,0,1,1}凉敲。
解題思路
這種荷蘭期問(wèn)題的核心解法很簡(jiǎn)單:ijk,ijk,ijk重要的事情說(shuō)三次衣盾，為什么是ijk呢，因?yàn)榻膺@種問(wèn)題需要定義3個(gè)指針配合運(yùn)算爷抓，
[0,i)i左邊的元素都是-1,
[i,j)中間的元素都是0,
(k, arr.length-1] k右邊的元素的都是1,
比較簡(jiǎn)單就不多做分析了势决，直接上代碼。
Code
public class RainbowSortTest {
@Test
public void test() throws Exception {
int[] arr = new int[]{1, -1, 0, 1, -1, 0};
rainbowSort(arr);
System.out.println(Arrays.toString(arr));
}
public int[] rainbowSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr;
}
int i = 0, j = 0, k = arr.length - 1;
while (j <= k) {
if (arr[j] == -1) {
swap2(arr, i, j);
i++;
j++;
} else if (arr[j] == 0) {
j++;
} else if (arr[j] == 1) {
swap2(arr, j, k);
k--;
}
}
return arr;
}
//交換數(shù)組的元素 實(shí)現(xiàn)2蓝撇，在函數(shù)調(diào)用次數(shù)巨大的情況下可以提高一些效率
private void swap2(int[] arr, int index1, int index2) {
if (index1 == index2) return;
arr[index1] = arr[index1] + arr[index2];
arr[index2] = arr[index1] - arr[index2];
arr[index1] = arr[index1] - arr[index2];
}
//交換數(shù)組的元素
private void swap1(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}
時(shí)空復(fù)雜度
一個(gè)循環(huán)無(wú)嵌套果复，時(shí)間復(fù)雜度O(n)，沒(méi)有使用多余的數(shù)組或遞歸空間復(fù)雜度O(1).
