1

这是一项学校作业，但是，要求是“以最高性能实施该程序”-这对我的口味来说是模糊的，因为我不知道内存是否会超过速度等等。但是我在寻找什么是否存在通过对输入数据进行一些智能操作来解决问题的“棘手”方法。

所以，问题来了：假设你有两个数组，A 和 B，编写一个函数，如果 B 中有这样的整数，则返回 1，它等于 A 的任何两个后续元素的总和。

下面是我的文案。请注意，我没有使用Hashmap<Integer>，因为我认为加速所需的内存是一个劣势，足以忍受 O(n * m) 速度作为我最坏的情况而不是 O(n)。

public static int arrayContainsSum(int[] a, int[] b)
{
    int offsetA = a.length - 1;
    int offsetB = offsetA;
    int index = b.length - 1;
    int result = 0;
    int tested;

    while (index >= 0)
    {
        if (offsetA > 0) a[offsetA] += a[--offsetA];
        else if (offsetA == 0) // This has a danger of overflowing the int
            a[offsetA--] = multiply(a);
        tested = b[index];
        if ((offsetA < 0 && tested != 0 && a[0] % tested != 0) ||
            offsetB == 0)
        {
            // No point to test this element as it doesn't 
            //divide the product of sums
            offsetB = a.length - 1;
            index--;
        }
        if (tested == a[offsetB--])
        {
            result = 1;
            break;
        }
    }
    return result;
}

private static int multiply(int[] input)
{
    int accumulator = input.length > 0 ? 1 : 0;
    for (int i : input)
        if (i != 0) accumulator *= i;
    return accumulator;
}

有些事情我不关心：整数溢出（可能是乘法的结果）。我假设array.length与从局部变量中读取一样快。

但是，再一次，我的问题是“不能分析地解决这个问题吗？” 这意味着更高的效率？

PS。问题没有提到数组是否只包含唯一成员 - 对此没有限制。我还认为可以通过排序来优化（如果我检测到这种情况），a以便如果b[x]小于 中的最小元素a或大于 中的最大元素a，它将节省一些查找 - 但是，这又是会以增加复杂性为代价，可能不完全合理。

4

3 回答 3

1 
public static int arrayContainsSum(int[] a, int[] b) {
  final Set<Integer> sums = new HashSet<Integer>();
  for (int i = 0; i < a.length - 1; i++) sums.add(a[i] + a[i+1]);
  for (int x : b) if (sums.contains(x)) return 1;
  return 0;
}
于 2012-04-28T21:40:42.100 回答
0

如有疑问，请使用蛮力。

好吧 - 当然，如果任务是编写一个高性能的解决方案，那可能还不够，但在优化解决方案之前，您需要一个解决方案。

val a = List (3, 9, 7, 4, 16)    
val b = List (29, 12, 21, 16, 18, 14) 

for (i <- (0 to a.length - 2); 
  j = i+1;
  if b.exists (_ == a(i)+a(j))) yield (a(i), a(j), a(i)+a(j))

它多久运行一次？外部循环从 1 运行到 array-length-1（这里是一个列表）以产生 i，j 只是后续元素。

但是对于 b 它总是贯穿整个数组，

如果按值对 b 进行排序，则可以在 b 中进行二进制查找。我猜规则中不允许使用 HashMap，因为您有两个数组。否则 HashMap 更快。

于 2012-04-28T21:47:32.723 回答
0

除非您有超过 100 万个元素并且需要超过 1 秒，否则速度无关紧要。顺便说一句，您不想制作超过 100 万个元素的数组。

不幸的是，Java 版本高达 7 甚至不包含基本的集合操作。但是，您可以在Google Guava库中找到它们（该代码经过适当测试并且尽可能高效）。

假设您有 2 组 20 个元素，a并且b- 从 1 到 100 和 200 中随机选择。

a = RandomInteger[{100}, 20]
b = RandomInteger[{200}, 20]

之后，您想找到a后续元素之和的集合中的哪些元素与b

ap = Table[Total[{a[[i]], a[[i + 1]]}], {i, 1, Length[a] - 1}]
Intersection[ap, b]

例如：

{73,43,99,33,80,35,54,82,50,23,92,22,54,4,14,14,8,80,92,85}
{121,139,158,158,51,176,65,84,76,172,73,148,71,128,55,134,4,32,183,134}
{116,142,132,113,115,89,136,132,73,115,114,76,58,18,28,22,88,172,177}
{73,76,172}
于 2012-04-28T21:13:11.227 回答