前段时间,我在面试中被要求对两个数组表示的整数求和,并将解放入另一个数组中。采访的一部分想法是让我提供一个有效的解决方案。从那以后,我一直在寻找一个简单有效的解决方案来解决这个问题,但我还没有找到。
所以我想与社区分享我的解决方案,并询问是否有任何人可以帮助提高效率。这个例子看起来像 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 中看到此代码的工作测试版本
最佳答案
正如 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[] {});
}
关于java - 如何有效地添加由两个数组表示的两个整数,将解决方案放入另一个数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58073566/