且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

查找数组是否平衡的算法

更新时间:2023-02-26 18:08:56

如果我理解这个问题,最简单的解决方案是这样的:

If I understand the question, the simplest solution is something like this:

def balanced(numbers):
    for pivot in range(len(numbers)):
        left_total = sum(numbers[:pivot])
        right_total = sum(numbers[pivot:])
        if left_total == right_total:
            return pivot
    return None

例如:

>>> numbers = [2, 1, 3, 0]
>>> balanced(numbers)
2
>>> more_numbers = [2, 1, 3, 4]
>>> balanced(numbers)

(那没有打印任何内容,因为它返回了,这意味着没有平衡列表的要点。)

(That didn't print anything, because it returned None, meaning there is no pivot to balance the list around.)

这是最简单的解决方案,它显然不是最有效的,因为您不断将相同的数字一遍又一遍地加起来。

While this is the simplest solution, it's obviously not the most efficient, because you keep adding the same numbers up over and over.

,很容易弄清楚如何保持 left_total right_total 的运行总计,仅调用 sum 一次。

If you think about it, it should be pretty easy to figure out how to keep running totals for left_total and right_total, only calling sum once.

def balanced(numbers):
    left_total, right_total = 0, sum(numbers)
    for pivot, value in enumerate(numbers):
        if left_total == right_total:
            return pivot
        left_total += value
        right_total -= value
    return None






最后,这是围绕它构建程序的方法:


Finally, here's how you can build a program around it:

size = 10
numbers = [random.range(4) for _ in range(size)]
pivot = balanced(numbers)
if pivot is None:
    print('{} is not balanced'.format(numbers))
else:
    print('{} is balanced, because elements 1-{} equal {}-{}'.format(
        numbers, pivot+1, pivot+2, size+1))