切割和堆叠阵列
我有一个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)。对于第四个数字,我们再次增加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
我将如何解决这一问题?
更新:我解决了它,并张贴了我自己的答案。但我仍然很好奇,其他人如何解决这个问题。请随时回答。
我认为如果您使用基于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 ..位顺序颠倒。
啊!但是如果输入数组不是“{1,2,3,4,5,6,7,8}”,而是一些随机的正整数? '{12,5,8,9,156,55,78,12}'?那么它不会在这种情况下工作,我认为 –
只需使用索引。 – jq170727
我正要删除我的评论。因为我意识到他们是指数。这是一个非常独特的解决方案。你是怎么想出来的? –
我解决使用两个火炮队列和一个主队列它:
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
请选择一个* *语言。然后编辑您的问题以将该语言作为标记,并且还包括您已经尝试过的[最小,完整和可验证示例](http://*.com/help/mcve)以及对它的描述没有按预期工作。如果你最近没有做过,那么请花一些时间再读一遍[阅读如何提出好问题](http://*.com/help/how-to-ask)。 –