java - 将数组减半，填充它，然后重新减半

Question

我正在尝试编写一个算法，该算法应该采用一个数组，将其分成两半并用 0 填充一半，将数组的其余部分分成两半并用 1 填充其中的一半，依此类推直到所有元素都被填满。 8 个字符的数组看起来像 [0 0 0 0 1 1 2 3]。我已经做了很多事情来为此编写代码，但总是要么陷入无限循环，要么最终抛出空指针异常。我的代码如下。有什么指点吗？

public Integer[] generateTestDataHalfs(int size)
    {
        //Generate the array
        Integer[] randHalfs = new Integer[size];

        //Use an integer to store the location of the array
        int arrPlace;
        int currNum = 0;
        int arrStart = 0;       //For the first iteration, start of the array

        //Half the size and set arrPlace to size + 1
        size /= 2;
        arrPlace = size + 1;

        //Use a while loop to populate the array
        while (size > 1)
        {
            //Populate part of the array
            for (int x = arrStart; x == size; x++)
            {
                randHalfs[x] = currNum;
            }

            //Increment the number
            currNum++;

            //Set it to the next part of the array
            size = randHalfs.length - arrPlace;
            size /= 2;
            arrPlace = size + 1;
            arrStart = arrPlace;
        }

        //Return the new array
        return randHalfs;
    }

Answer 1

我在代码中看到的第一个问题是 for 循环:终止条件 x == size 将计算为 false (并且立即终止循环)除非size == arrStart。您不希望这样，因为这意味着数组的一部分不会被填充。第二个问题是，如果 size == 1，您将不会初始化(子)数组中的任何内容，这也是错误的。我无法解释无限循环，但可能存在数组长度，其中 size 每次通过 while 循环都不会更改值。您可以通过使用调试器单步执行或每次通过循环记录变量值来诊断此类情况。

无论如何，您的代码都可以大大简化。我的版本如下所示:

public Integer[] generateTestDataHalfs(int size) {
    Integer [] result = new Integer[size];
    Integer fillValue = 0;
    int start = 0;
    while (start < size) {
        int fillLength = (size - start) / 2;
        // check for final element
        if (fillLength == 0) {
            // fill final element
            fillLength = 1;
        }
        for (int i = 0; i < fillLength; i++) {
            result[start + i] = fillValue;
        }
        fillValue++;
        start += fillLength;
    }
    return result;
}

您没有指定当数组长度不是 2 的幂时会发生什么(因此某些子数组不会分成相等的两半)。在上面，我假设前半部分应该更短。如果您希望后半部分更短，只需将初始化 fillLength 的行更改为:

int fillLength = (size + 1 - start) / 2;