java - 使用java对数组进行二进制分区

Question

我是一名初学者(大学一年级学生)程序员，试图解决这个我发现有些困难的问题。如果你要回答这个问题，请不要向我提供一个复杂的令人畏惧的算法，这会让我摸不着头脑。如果您解释一下我的步骤(逻辑上/概念上然后通过代码)，我将非常感激

问题如下:image

我尝试过，但我的代码仅适用于我测试的特定情况。

package com.company;
import java.lang.Math;

public class Main {

public static int[][] binary_partition(int array[], int k){
    int x = (int) Math.pow(2,k);
    int[][] partition = new int[((array.length/x)*2)][array.length/x];
    int divisor = array.length/x;

    if ((array.length % 2) != 0){
        return partition;
    }
    if (divisor >= array.length-1){
        return partition;
    }
    if (k==1){
        return partition;
    }

    int p = 0;
    for(int i=0;i<((array.length/x)*2);i++)
    {
        for (int j = 0; j<array.length/x;j++)
        {
            partition[i][j] = array[p];
            p += 1;
        }
    }
    return partition;
}

public static void main(String[] args){
    int[] array = {3, 2, 4, 7, 8, 9, 2, 3};
    int[][] result = binary_partition(array,2);

    for (int[] x : result){
        for (int y : x)
        {
            System.out.print(y + " ");
        }
        System.out.println();
    }
  }
}

Answer 1

您的问题不清楚，但此解决方案创建了一个函数，将具有正确长度的数组划分为 2^k 组。
首先，一个有趣的事实:使用位移运算符<<一个整数的值增加了 2 的幂。因此，要找出分区的大小，您可以编写

int numPartitions = 1 << k; // Equivalent to getting the integer value of 2^k

有了这个事实，函数就变成了

public static int[][] partition(int[] set, int k) {
    if (set == null)
        return null; // Don't try to partition a null reference

    // If k = 0, the partition of the set is just the set
    if (k == 0) {
        int[][] partition = new int[1][set.length];
        // Copy the original set into the partition
        System.arraycopy(set, 0, partition[0], 0, set.length);
        return partition;
    }

    int numPartitions = 1 << k; // The number of sets to partition the array into
    int numElements = set.length / numPartitions; // The number of elements per partition

    /* Check if the set has enough elements to create a partition and make sure
       that the partitions are even */
    if (numElements == 0 || set.length % numElements != 0)
        return null; // Replace with an error/exception of your choice

    int[][] partition = new int[numPartitions][numElements];
    int index = 0;

    for (int r = 0; r < numPartitions; r++) {
        for (int c = 0; c < numElements; c++) {
            partition[r][c] = set[index++]; // Assign an element to the partition
        }
    }

    return partition;
}