【題目】

　　給定一個(gè)有序數(shù)組arr，調(diào)整arr使得這個(gè)數(shù)組的左半部分沒有重復(fù)元素且升序，而不用保證右部分是否有序

　　例如，arr=[1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9]，調(diào)整之后arr=[1, 2, 3, 4, 5, 6, 7, 8 ,9, ...]

?

【要求】

　　時(shí)間復(fù)雜度為O(N)，額外空間復(fù)雜度為O(1)

?

1 public void leftUniqueSort(int[] arr) 2 { 3 if(arr == null || arr.length < 2) 4 { 5 　　return; 6 } 7 8 int left = 0; 9 int cur = 1; 10 11 while(cur != arr.length) 12 { 13 　　if(arr[cur] != arr[left]) 14 　　{ 15 　　swap(arr, ++left, cur); 16 　　} 17 　　cur++; 18 } 19 }

?

?

【題目】

　　給定一個(gè)數(shù)組arr，其中只可能含有0、1、2三個(gè)值，請(qǐng)實(shí)現(xiàn)arr的排序

?

【要求】

　　時(shí)間復(fù)雜度為O(N)，額外空間復(fù)雜度為O(1)

1 public void sort(int[] arr) 2 { 3 if(arr == null || arr.length < 2) 4 { 5 　　return; 6 } 7 8 int left = -1; 9 int index = 0; 10 int right = arr.length; 11 12 while(index < right) 13 { 14 　　if(arr[index] == 0) 15 　　{ 16 　　 swap(arr, ++left, index++); 17 　　} 18 　　else if(arr[index] == 2) 19 　　{ 20 　　swap(arr, index, --right); 21 　　} 22 　　else 23 　　{ 24 　　index++; 25 　　} 26 } 27 }

?

?

【題目】

　　有一個(gè)數(shù)組arr，給定一個(gè)值k，實(shí)現(xiàn)比k小的數(shù)都放在數(shù)組的左邊，等于k的數(shù)都放在數(shù)組的中間，大于k的數(shù)都放在數(shù)組的右邊

?

【要求】

　　時(shí)間復(fù)雜度為O(N)，額外空間復(fù)雜度為O(1)

1 public void sort(int[] arr, int k) 2 { 3 if(arr == null || arr.length < 2) 4 { 5 　　return; 6 } 7 8 int left = -1; 9 int index = 0; 10 int right = arr.length; 11 12 while(index < right) 13 { 14 　　if(arr[index] < k) 15 　　{ 16 　　swap(arr, ++left, index++); 17 　　} 18 　　else if(arr[index] > k) 19 　　{ 20 　　swap(arr, index, --right); 21 　　} 22 　　else 23 　　{ 24 　　index++; 25 　　} 26 } 27 }

?

1 public void swap(int[] arr, int i, int j) 2 { 3 int temp = arr[i]; 4 arr[i] = arr[j]; 5 arr[j] = temp; 6 }

?

來(lái)源：左程云老師《程序員代碼面試指南》

轉(zhuǎn)載于:https://www.cnblogs.com/latup/p/10943598.html

總結(jié)

以上是生活随笔為你收集整理的Coding Interview Guide -- 数组的partition调整的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。