給定數(shù)組 arr，請將數(shù)組調(diào)整成 a <= b >= c <= d >= e <= f...的樣子

例如，arr = {3,1,2}
調(diào)整之后，arr 可以是{1,3,2}. 1 <= 3 >=2
調(diào)整之后，arr 也可以是{2,3,1}. 2 <= 3 >=1
arr = {3,1,2,6}
調(diào)整之后，arr 可以是{1,6,2,3}. 1 <= 6 >= 2 <= 3
調(diào)整之后，arr 也可以是{3,6,1,2}. 3 <= 6 >= 1 <= 2

1，如果 arr 長度為 N，要求時間復(fù)雜度為 O(N)，額外空間復(fù)雜度為 O(1)。
2，arr 可能會不止一種調(diào)整方案，但只要滿足要求即可。


算法原形：完美洗牌算法

public static void shuffle(int[] arr, int l, int r){while(r - l + 1 > 0){int lenAndOne = r - l + 2;int bloom = 3;int k = 1;while(bloom <= lenAndOne / 3){bloom += 3;k++;}int m = (bloom - 1) / 2;int mid = (l + r) / 2;rotate(arr, l + m, mid, mid+m);cycles(arr, l - 1, bloom, k);l = l + bloom - 1;} }public static void cycles(int[] arr, int base, int bloom, int k){for(int i = 0, trigger = 1; i < k; i++, trigger += 3){int next = (2*trigger) % bloom;int cur = next;int record = arr[next + base];int tmp = 0;arr[next + base] = arr[trigger + base];while(cur != trigger){next = (2 * cur) %bloom;tmp = arr[next + base];arr[next + base] = record;cur = next;record = tmp;}} }public static void rotate(int[] arr, int l, int m, int r){reverse(arr, l, m);reverse(arr, m + 1, r);reverse(arr, l ,r); }public static void reverse(int[] arr, int l, int r){while(l < r){int tmp = arr[l];arr[l++] = arr[r];arr[r--] = tmp;} }

總結(jié)

以上是生活随笔為你收集整理的数组先小于等于再大于等于的调整的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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