剪切并堆叠数组

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数组

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).对于第四个数字,我们增加i的n一次.我想知道是否有模式？或者你解决这个问题的方法是什么？我正在寻找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 ..顺序颠倒了.