如何构建二维数组金字塔？求build(int n)实现及数组大小预测方案

Great question! Let's break this down step by step to build that pyramid array correctly.

Step 1: Figure Out the Array Dimensions #

First, let's analyze your example: build(6) returns a 3-row, 5-column array. Let's spot the patterns here:

• Number of rows (k): This is the smallest integer where the sum 1+2+...+k (a triangular number) is greater than or equal to n. For n=6, 1+2+3=6 exactly, so k=3. For n=5, 1+2+3=6≥5 so k=3 too; for n=1, k=1.
  To calculate k programmatically, we can use a formula derived from solving the triangular number equation:

  int k = (int) Math.ceil((Math.sqrt(8 * n + 1) - 1) / 2);
  

• Number of columns (cols): Every row has the same number of columns, which is an odd number equal to 2*k - 1. For k=3, that's 2*3-1=5—matching your example. For k=2, cols would be 3.

Step 2: Fill the Array with Numbers #

Once we have the dimensions, filling the numbers is straightforward:

1. Initialize a k x cols array with all zeros (Java does this automatically when creating the array).
2. Start with the number 1 and iterate through each row:
   • For row i (0-indexed):
     • If it's the last row, calculate how many numbers we need to place: n - (k-1)*k/2 (since the first k-1 rows hold (k-1)*k/2 numbers total). For non-last rows, we place i+1 numbers (1 number in row 0, 2 in row 1, etc.).
     • The first number in row i starts at position cols/2 - i—this keeps the numbers centered in the pyramid. We then skip one index each time (add 2 to the position) to place the next number.

Full Java Implementation #

Here's the complete method with test code:

public class PyramidBuilder {
    public static int[][] build(int n) {
        // Handle edge case for non-positive n
        if (n <= 0) {
            return new int[0][0];
        }
        
        // Calculate number of rows k
        double sqrtResult = Math.sqrt(8 * n + 1);
        int k = (int) Math.ceil((sqrtResult - 1) / 2);
        
        int cols = 2 * k - 1;
        int[][] pyramid = new int[k][cols];
        
        int currentNumber = 1;
        for (int row = 0; row < k; row++) {
            // Determine how many numbers go in this row
            int numbersInRow;
            if (row == k - 1) {
                numbersInRow = n - (k - 1) * k / 2;
            } else {
                numbersInRow = row + 1;
            }
            
            // Starting position for the first number in the row
            int currentPos = cols / 2 - row;
            
            // Place each number in the row
            for (int i = 0; i < numbersInRow; i++) {
                pyramid[row][currentPos] = currentNumber++;
                currentPos += 2;
            }
        }
        
        return pyramid;
    }

    // Test the method with your example
    public static void main(String[] args) {
        int[][] result = build(6);
        for (int[] row : result) {
            System.out.println(java.util.Arrays.toString(row));
        }
        // Output matches your example:
        // [0, 0, 1, 0, 0]
        // [0, 2, 0, 3, 0]
        // [4, 0, 5, 0, 6]
    }
}

Edge Case Checks #

• n=1: Returns {{1}} (correct single-element pyramid)
• n=2: Returns {{0,1,0}, {2,0,0}}
• n=5: Returns {{0,0,1,0,0}, {0,2,0,3,0}, {4,0,5,0,0}}

内容的提问来源于stack exchange，提问作者Ladence