如何根据列表长度获取二维表示的最优矩阵尺寸？

问题描述 #

给定长度动态变化的列表，需找到能容纳所有元素的最优矩阵尺寸（width × height），要求：

• 矩阵总容量 ≥ 列表长度（width * height ≥ len(a)）
• 优先选择宽度与高度差值最小的组合；若存在多个候选，优先选宽度≥高度的（参考示例）

示例 #

示例1：
输入列表：a = [1, 2, 3, 3, 2, 1, 3]（长度7）
预期输出：width: 3 height: 3
说明：3×3=9≥7，是差值最小的有效组合

示例2：
输入列表：a = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4]（长度13）
预期输出：width: 4 height: 4（注：原示例输出4×3的容量为12<13，无法容纳所有元素，应为笔误）

现有代码问题 #

你当前的代码逻辑存在偏差，通过遍历生成候选列和行再交叉匹配的方式，会产生无效候选且效率低下，最终可能错过更优解或生成错误解。现有代码：

a = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4]
cols, rows = [],[]
for id in range(1, len(a)):
    if id * (abs(id-len(a))) >= len(a):
        cols.append(id)
        rows.append(abs(id-len(a)))
x,y,z=[],[], []
for col in cols:
    for row in rows:
        if row*col >= len(a):
            x.append(col)
            y.append(row)
            z.append(abs(col-row))
index = z.index(min(z))
print(f'width: {x[index]}', f'height: {y[index]}')

输出：width: 4 height: 4

正确实现思路 #

最优矩阵的尺寸必然围绕列表长度的平方根附近，因为平方根是宽度和高度最接近的点。核心步骤：

1. 计算列表长度n = len(a)
2. 从n的整数平方根开始，遍历可能的宽度值
3. 对每个宽度，计算所需的最小高度（向上取整n/width），确保容量足够
4. 记录差值最小的组合，若差值相同则保留宽度≥高度的组合

正确代码实现 #

import math

def find_optimal_matrix(a):
    n = len(a)
    if n == 0:
        return (0, 0)
    
    min_diff = float('inf')
    best_width, best_height = n, 1
    sqrt_n = math.isqrt(n)
    
    # 从平方根附近开始遍历，优先找宽度≥高度的组合
    for width in range(sqrt_n, n + 1):
        height = (n + width - 1) // width  # 等价于向上取整n/width
        current_diff = abs(width - height)
        
        if current_diff < min_diff:
            min_diff = current_diff
            best_width, best_height = width, height
            if min_diff == 0:  # 找到完全匹配的正方形，直接返回
                break
    
    # 检查平方根以下的宽度，避免漏掉宽度<高度但差值更小的情况
    for width in range(1, sqrt_n):
        height = (n + width - 1) // width
        current_diff = abs(width - height)
        if current_diff < min_diff:
            min_diff = current_diff
            best_width, best_height = width, height
    
    # 确保最终输出宽度≥高度（符合常规习惯）
    if best_width < best_height:
        best_width, best_height = best_height, best_width
    
    return (best_width, best_height)

# 测试示例1
a1 = [1, 2, 3, 3, 2, 1, 3]
w1, h1 = find_optimal_matrix(a1)
print(f'width: {w1} height: {h1}')  # 输出: width: 3 height: 3

# 测试示例2
a2 = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4]
w2, h2 = find_optimal_matrix(a2)
print(f'width: {w2} height: {h2}')  # 输出: width: 4 height: 4

代码说明 #

• math.isqrt(n)获取n的整数平方根（向下取整），缩小遍历范围，提升效率
• (n + width - 1) // width是计算向上取整的高效写法，避免浮点运算误差
• 先遍历平方根以上的宽度，优先保证宽度≥高度的组合；再遍历平方根以下的，避免遗漏更优解
• 最后调整宽度和高度，确保输出符合常规展示习惯

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