4

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

这是面试材料中的一个问题,不是家庭作业

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

4

3 回答 3

7

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

如果您想防止溢出,以下是如何在原地和线性时间内执行它:

  • 将数组就地拆分为其负条目(以任何顺序)和其正条目(以任何顺序)。零可以在任何地方结束。换句话说,在枢轴为零的情况下执行一个快速排序步骤。

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

  • pi指向数组的末尾。
  • 设为sum零。
  • 尽管pi >= ni

    • 如果sum是负数
      • 添加arr[pi]sum.
      • 如果arr[pi]为负(我们已经用完了正加数)并且sum为正(发生溢出),则结果溢出。
      • 递减pi
    • 别的
      • 添加arr[ni]sum.
      • ifarr[ni]为正且sum为负,结果溢出。
      • 增量ni
  • 最后,检查是否sum有多个K位。如果是,则声明结果溢出。

于 2013-01-27T07:42:43.280 回答
2

主要思想是使用两个索引迭代数组:正元素和负元素。当总和为负时,我们将搜索下一个正元素(使用相应的迭代器)以添加到总和中,否则 - 为负元素。

此代码应该可以工作:

public final class ArrayAdder {
  @NotNull
  private final int[] array;

  private int sum;

  public ArrayAdder(@NotNull int[] array) {
    this.array = array;
  }

  public int sum() {
    sum = 0;

    final IntPredicate positive = v -> v > 0;
    final Index positiveIndex = new Index(positive);
    final Index negativeIndex = new Index(positive.negate());

    while (positiveIndex.index < array.length || negativeIndex.index < array.length) {
      sum += sum < 0 ? sum(positiveIndex, negativeIndex) : sum(negativeIndex, positiveIndex);
    }

    return sum;
  }

  private int sum(@NotNull Index mainIndex, @NotNull Index secondaryIndex) {
    int localSum = 0;
    // searching for the next suitable element
    while (mainIndex.index < array.length && secondaryIndex.sign.test(array[mainIndex.index])) {
      mainIndex.index++;
    }

    if (mainIndex.index < array.length) {
      localSum += array[mainIndex.index++];
    } else {
      // add the remaining elements
      for (; secondaryIndex.index < array.length; secondaryIndex.index++) {
        if (secondaryIndex.sign.test(array[secondaryIndex.index])) {
          localSum += array[secondaryIndex.index];
        }
      }
    }
    return localSum;
  }

  private static final class Index {
    @NotNull
    private final IntPredicate sign;

    private int index;

    public Index(@NotNull IntPredicate sign) {
      this.sign = sign;
    }
  }
}
于 2017-03-07T09:28:04.710 回答
0

选项 1:就地对数组进行排序并迭代其中的一半。在每一步,将第ith 元素与第size-i-1th 元素相加。

如果有一些大数字但有很多小的负数(反之亦然),则不起作用。

选项 2(改进):

就地排序。

保留两个索引 - 一个在开头,一个在结尾。当他们相遇时退出一个循环。如果到目前为止的结果是负数,则在每一步中添加第二个索引处的值并推进它。如果结果是肯定的,则在第一个索引处添加值并推进它。

于 2013-01-27T07:14:35.183 回答