切割和堆疊陣列

Question

我有一個array的int作爲輸入。數組總是長度爲2^n。我想把數組切成兩半並堆疊起來。重複切割和堆疊，直到只有一個堆疊。例如：

int[] array = {1,2,3,4,5,6,7,8}

如果我們削減了一半的陣列，我們和堆棧他們來說，這將是：

{1,2,| 3,4} 
{5,6,| 7,8} 

切割並重新堆棧：再次

{1,|2} 
{5,|6} 
{3,|4} 
{7,|8} 

：

{1} 
{5} 
{3} 
{7} 
{2} 
{6} 
{4} 
{8} 

所需的輸出將是整數的數組從頂部到堆棧

int[] output = {1,5,3,7,2,6,4,8} 

我曾嘗試通過循環輸入數組以特定的方式來構造輸出數組的末尾。請注意，當我到達陣列時，我只是再次從頭開始。我從array[i]開始，其中i = 0。我以這種方式得到第一個數字。那麼我增加i n，其中n是log(array.legnth)（基數2）。這是我如何得到第二個數字。對於第三個數字，我們增加i（n + n/2）。對於第四個數字，我們再次增加in。我想知道有沒有一種模式？或者你會怎樣解決這個問題？我正在尋找java或python中的解決方案。

---

編輯/更新：

我試圖用queue一種新的方法。我基本上保持切割數組的一半，並將數組的一半推入隊列，直到隊列中的數組全部長度爲2（或堆棧高度爲n）。但我的結果是不正確的。我認爲它與我將半數組添加回隊列的順序有關。

import java.util.*; 

public class StackArray{ 
    public static void main(String[] args){ 
     int[] array = {1,2,3,4,5,6,7,8}; 
     int[] answer = stackArray(array); 
     for(int n : answer){ 
      System.out.println(n); 
     } 
    } 

    public static int[] stackArray(int[] array){ 
     int height = (int) (Math.log(array.length)/Math.log(2)) + 1; 
     Queue<int[]> queue = new LinkedList<int[]>(); 
     ArrayList<Integer> list = new ArrayList<>(); 
     queue.add(array); 
     while(queue.size() < height){ 
      int currentLength = queue.size(); 
      int i = 0; 
      while(i < currentLength){ 
       int[] temp = queue.poll(); 
       int[] array1 = new int[temp.length/2]; 
       int[] array2 = new int[temp.length/2]; 
       System.arraycopy(temp, 0, array1, 0, array1.length); 
       System.arraycopy(temp, array1.length, array2, 0, array2.length); 
       queue.add(array1); //I think the problem is here 
       queue.add(array2); 
       i++; 
      } 

     } 


     int y = 0; 
     while(y < 2){ 

      for(int i = 0; i < queue.size(); i++){ 
       int[] curr = queue.poll(); 
       list.add(curr[y]); 
       queue.add(curr); 

      } 
      y++; 
     } 

     int[] ret = new int[list.size()]; 
     for(int i = 0; i < list.size(); i++){ 
      ret[i] =list.get(i); 
     } 

     return ret; 

    } 
} 

結果：

1 
3 
5 
7 
2 
4 
6 
8 

我將如何解決這一問題？

---

更新：我解決了它，並張貼了我自己的答案。但我仍然很好奇，其他人如何解決這個問題。請隨時回答。

Answer 1

我認爲如果您使用基於0的索引 並以二進制表示數字，則該模式變得清晰。例如

 0 1 2 3 4 5 6 7 
     000 001 010 011 100 101 110 111 

     0 1 2 3 
     000 001 010 011 
     100 101 110 111 
     4 5 6 7 


    0 = 000 001 = 1 
    4 = 100 101 = 5 
    2 = 010 011 = 3 
    6 = 110 111 = 7 

    0 = 000 
    4 = 100 
    2 = 010 
    6 = 110 
    1 = 001 
    5 = 101 
    3 = 011 
    7 = 111 

看到最左邊位的模式？該序列只是 數字0,1,2 ..位順序顛倒。

Answer 2

我解決使用兩個火炮隊列和一個主隊列它：

import java.util.*; 

public class StackArray{ 
    public static void main(String[] args){ 
     int[] array = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}; 
     int[] answer = stackArray(array); 
     for(int n : answer){ 
      System.out.println(n); 
     } 
    } 

    public static int[] stackArray(int[] array){ 
     int height = (int) (Math.log(array.length)/Math.log(2)) + 1; 
     Queue<int[]> queue = new LinkedList<int[]>(); 
     ArrayList<Integer> list = new ArrayList<>(); 
     Queue<int[]> queue1 = new LinkedList<int[]>(); 
     Queue<int[]> queue2 = new LinkedList<int[]>(); 
     queue.add(array); 
     while(queue.size() < height){ 
      int currentLength = queue.size(); 

      int i = 0; 
      while(!queue.isEmpty()){ 
       int[] temp = queue.poll(); 
       int[] array1 = new int[temp.length/2]; 
       int[] array2 = new int[temp.length/2]; 
       System.arraycopy(temp, 0, array1, 0, array1.length); 
       System.arraycopy(temp, array1.length, array2, 0, array2.length); 
       queue1.add(array1); //I think the problem is here 
       queue2.add(array2); 
       i++; 
      } 
      while(!queue1.isEmpty()){ 
       int[] temp1 = queue1.poll();  
       queue.add(temp1); 
      } 
      while(!queue2.isEmpty()){ 
       int[] temp2 = queue2.poll(); 
       queue.add(temp2); 
      } 

     } 


     int y = 0; 
     while(y < 2){ 

      for(int i = 0; i < queue.size(); i++){ 
       int[] curr = queue.poll(); 
       list.add(curr[y]); 
       queue.add(curr); 

      } 
      y++; 
     } 

     int[] ret = new int[list.size()]; 
     for(int i = 0; i < list.size(); i++){ 
      ret[i] =list.get(i); 
     } 

     return ret; 

    } 
} 

輸出;

1 
5 
3 
7 
2 
6 
4 
8 

也測試上，當n = 4：

1 
9 
5 
13 
3 
11 
7 
15 
2 
10 
6 
14 
4 
12 
8 
16