java - 查找没有溢出的整数数组的总和

Question

给定一个整数数组(正数和负数)，每个整数最多有 K 位(加上符号位)，已知数组中所有整数的总和也最多有 K 位(加上符号位)符号位)。设计一个算法来计算数组中整数的和，所有中间和也最多有 K 位(加上符号位)。 [提示:找出你应该以什么顺序添加正数和负数]。

这是面试题，不是作业

我实际上正在考虑创建两个单独的数组，一个用于正数，另一个用于负数，对它们进行排序，然后将两者相加，以便将最负数添加到最正数...但这似乎有 O(nlogn) 时间复杂度(排序)和 O(n) 空间复杂度> 请帮忙!

Answer 1

首先注意，即使你让即时结果溢出，如果能表示出来，最终结果总是正确的。这是因为在包括 Java 在内的大多数语言中，任何大小的整数类型都像加法下的循环组(不是在 C 中，整数溢出是未定义的行为，而 C# 会抛出溢出异常)。

如果您仍然想防止溢出，下面是如何在线性时间内就地执行它:

• 将数组就地拆分为负数项(以任何顺序)和正数项(以任意顺序)。零可以在任何地方结束。换句话说，执行一个以零为基准的快速排序步骤。

• 让 ni 指向数组的开头(负数项所在的位置)。

• 让pi指向数组的末尾。
• 设sum为零。

• 当 pi >= ni

  • 如果 sum 为负
    • 将 arr[pi] 添加到 sum。
    • 如果 arr[pi] 为负数(我们用完了正加数)并且 sum 为正数(发生溢出)，则结果溢出。
    • 递减 pi
  • 其他
    • 将 arr[ni] 添加到 sum。
    • 如果arr[ni]为正且sum为负，则结果溢出。
    • 增加ni。

• 最后，检查sum 是否超过K 位。如果是，则声明结果溢出。