java - 如何有效地添加由两个数组表示的两个整数，将解决方案放入另一个数组

Question

前段时间，我在面试中被要求对两个数组表示的整数求和，并将解放入另一个数组中。采访的一部分想法是让我提供一个有效的解决方案。从那以后，我一直在寻找一个简单有效的解决方案来解决这个问题，但我还没有找到。

所以我想与社区分享我的解决方案，并询问是否有任何人可以帮助提高效率。这个例子看起来像 O(mn)，其中 mn 是 m 或 n 之间最大数组的大小，其中 m 和 n 表示要求和的每个整数数组的大小。因此，它看起来好像是在线性时间内工作。

public class ArrayRudiments {

    /**
     * Add two integers represented by two arrays
     * 
     * NOTE: Integer as a natural number, not as a programming language data type.
     * Thus, the integer can be as big as the array permits.
     * 
     * @param m first number as array
     * @param n second number as array
     * @return integer sum solution as array
     */
    public Integer[] sum(Integer m[], Integer n[]) {
        int carry = 0, csum = 0;
        final Vector<Integer> solution = new Vector<Integer>();

        for (int msize = m.length - 1, nsize = n.length - 1; msize >= 0 || nsize >= 0; msize--, nsize--) {

            csum = (msize < 0 ? 0 : m[msize]) + (nsize < 0 ? 0 : n[nsize]) + carry;
            carry = csum / 10;

            solution.insertElementAt(csum % 10, 0);
        }

        if (carry > 0) {
            solution.insertElementAt(carry, 0);
        }

        return solution.toArray(new Integer[] {});
    }

}

这里的问题或技巧是非线性时间作业是由 Vector 类执行的，它插入新元素并调整解决方案数组的大小。这样，解决方案就不会在线性时间内工作。是否可以在没有 Vector 类的情况下创建类似的解决方案？

您还可以在 https://github.com/lalounam/rudiments 中看到此代码的工作测试版本

Answer 1

正如 SSP 在评论中所说，您应该创建一个初始容量为 Math.max(m.length, n.length) + 1 的 ArrayList .即和的最大位数。

int arrayCapacity = Math.max(m.length, n.length) + 1;
final List<Integer> solution = new ArrayList<>(arrayCapacity);

然后你需要用0填充:

for (int i = 0 ; i < arrayCapacity ; i++) {
    solution.add(0);
}

这是“技巧”。在主 for 循环中，您不是从头开始填充数组，而是从末尾开始填充。不是 insertElementAt 开始，而是 set 元素在我们迭代的任何索引处，加上 1，因为 solution 比 longer m 和 n。

solution.set(Math.max(msize, nsize) + 1, csum % 10);

这实际上是“从后面”填充列表。

最后你像这样调整列表的大小:

if (carry > 0) {
    solution.set(0, carry);
    return solution.toArray(new Integer[] {});
} else {
    return solution.subList(1, solution.size()).toArray(new Integer[] {});
}