給定一個數組[1, 2, 3, a, b, c]
,編寫一個方法重新排列數組,使其他元素都改變其位置。輸出應該是[1, a, 2, b, 3, c]
。交替排列元素的順序
1.寫一個algorithm
,其工作更快,並使用O(1)
空間。 2.如果允許一個extra-space
,可以實現多大的改進time-complexity
。
這是一個面試問題。在SO,Interview test - rearrange the array,Reordering of array elements,,Array movement from a1,..,an,b1,..,bn to a1,b1,..,an,bn和elsewhere有幾個職位,其中提供了各種解釋,但對我來說它不明確和具體。 對於上面的第一個問題,我有一個O(n^2)
解決方案。但似乎有可能改善它。但我真的不會在這些帖子中解釋,尤其是一些提到理論論文的人。如果針對第一個問題的時間複雜度提高(比O(n^2)
更好)的簡單僞代碼會很棒
對於第二個問題,通過使用一個存儲陣列可以將時間複雜度降低到O(n)
。 但我沒有看到任何進一步改進的方法。如果可能的話,我會很樂意聽到它。
我第一次嘗試的代碼(不使用auxillary存儲)是在這裏:
import java.util.Arrays;
public class SwapHalfArrayElements {
public static void main(String[] args){
Object[] arr = {1,2,3,'a','b','c'};
System.out.println("before sorting "+Arrays.toString(arr));
rearrageArray(arr);
System.out.println("After sorting "+ Arrays.toString(arr));
}
private static void swap(Object[] arr, int index1, int index2){
Object temp=arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
}
private static void rearrageArray(Object[] arr){
int n=arr.length/2;
for (int i=1;i<n;i++){
for (int j=-i;j<i;j+=2){
swap(arr,n+j,n+j+1);
}
}
}
}
你能詳細解釋一下,如何將第一個數組轉換爲輸出數據?似乎無法弄清楚。 – Warlord
@Warlord:我從數組中間開始交換並向外發展 –