Couper et empiler la matrice

Question

J'ai une array de int comme entrée. Le tableau aura toujours une longueur de 2^n. Je veux couper le tableau en deux et l'empiler. Répétez la coupe et l'empilage jusqu'à ce qu'il n'y ait plus qu'une seule pile. Par exemple:

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

si on coupe le tableau en deux nous et empilez ce serait:

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

couper et empiler à nouveau:

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

nouveau:

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

la sortie désirée serait un tableau d'entiers à partir du haut à l'extrémité de la pile

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

j'ai essayé de construire le tableau de sortie par bouclage du tableau d'entrée d'une manière particulière. Notez que lorsque j'atteins le tableau, je recommence à partir de la tête. Je commence à array[i] où i = 0. Je reçois le premier numéro de cette façon. alors j'incrémente i par n où n est le log(array.legnth) (base 2). C'est comme ça que je reçois le deuxième numéro. Pour le troisième nombre, nous incrémentons i par (n + n/2). Pour le quatrième chiffre, nous incrémentons à nouveau i par n. Je me demande s'il y a un modèle? Ou quelle serait votre approche pour résoudre ce problème? Je suis à la recherche d'une solution en Java ou en python.

---

Modifier/Mise à jour:

j'ai essayé une nouvelle approche à l'aide queue. Je continue fondamentalement à couper le tableau en deux et à pousser les deux moitiés du tableau dans la file d'attente jusqu'à ce que les tableaux dans la file d'attente aient tous une longueur de 2 (ou que la pile soit à la hauteur n). mais mon résultat n'est pas correct. Je pense que cela a à voir avec l'ordre que j'ajoute les demi-tableaux dans la file d'attente.

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; 

    } 
} 

Résultat:

1 
3 
5 
7 
2 
4 
6 
8 

comment pourrais-je résoudre ce problème?

---

mise à jour: Je l'ai résolu et posté ma propre réponse. mais je suis toujours curieux de savoir comment les autres pourraient résoudre cela. Merci de ne pas hésiter à répondre.

Answer 1

Je pense que le modèle devient clair si vous utilisez les 0-index et exprimez des nombres en binaire. par exemple

 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 

voir le motif dans les bits les plus à gauche? la séquence est juste les nombres 0,1,2 .. avec l'ordre des bits inversé.

Answer 2

I résolus à l'aide de deux files d'attente d'artillerie et une file d'attente principale:

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; 

    } 
} 

sortie;

1 
5 
3 
7 
2 
6 
4 
8 

tester également lorsque n = 4:

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