切割和堆叠阵列

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