0

这是我获取数组索引的代码，其值的总和对应于给定的目标值。目前最坏的情况是 O(N2) 算法。有什么改进的方法吗？ 

public class SumArrayTarget {

public static void main(String[] args) {
        int[] arr = { 1, 2, 4, 6, 3, 5, 7 };
        System.out.println("The indices are "+ Arrays.toString(sum(arr, 12)));
    }

    public static int[] sum(int[] arr, int target) {
        int[] list = new int[2];
        for (int i = 0; i < arr.length - 1; i++) {
            int j = i+1;
            while (j < arr.length) {
                if (arr[i] + arr[j++] == target){
                    list[0]=i;
                    list[1]=j-1;
                    return list;
                }
            }
        }
        return list;
    }
}
4

3 回答 3

1

您的算法假设总有两个数字加起来达到所需的目标。如果没有，则返回索引 {0,0} 的空列表。如果这是您需要的行为，那么我能想到的复杂性有一个改进：

  • 将输入数组放入 LinkedHashMap，将数字映射为键，将其索引映射为值。花费 O(n) 时间。
  • 遍历地图。对于每个带有 key 的项目n：
    • 查看 map 中是否有带有 key 的元素，如果有target - n，则返回一个包含两个键的数组。每个元素花费预期的 O(1) 时间。
  • 如果地图的任何元素都没有相应的答案，则返回 null 或其他内容以指示没有答案可能。

这使算法的总运行时间达到了预期的 O(n)，但开销却很大。对于小于一百万的输入数组，您的蛮力方法可能更好。

如果您尝试回答的问题也允许两个以上的索引作为结果，那么您就遇到了整数背包问题。你可以用谷歌搜索，但它变得更加复杂！

编辑：添加示例实现。

public static int[] sum(int[] arr,int target) {
    LinkedHashMap<Integer,Integer> map = new LinkedHashMap<Integer>(arr.length);
    for(i = 0;i < arr.length;i++) {
        map.add(arr[i],i);
    }
    for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
        int n = entry.getValue();
        int index = entry.getKey();
        if(map.containsKey(target - n)) {
            return new int[] {index,map.get(target - n)};
        }
    }
    return null;
}
于 2013-08-30T02:01:25.243 回答
0

对于一个非常大的数组，您可以通过对数组进行排序（即arrO(N log N)）使其成为 O(N log N)，然后对于每个元素arr[i]，在数组的其余部分到最后一个元素寻找。二分查找是 O(log N)，所以整个算法是 O(N log N)。这需要一个相当大的 N 才能使这变得有价值——比 7 大得多。arr[i+1]target - arr[i]

您可以在当前代码中节省一点时间：（1）如果您x = target - arr[i]在开始内部循环之前进行计算，并检查arr[j++] == x内部循环内部。(2) 如果您知道问题的一个条件是 的所有元素arr都是正数，那么在x按上述计算后，您可以完全跳过内循环 if x <= 0。

PS 如果没有找到结果，请确保您知道要返回的内容。您当前的代码将返回一个 2 元素数组，其中两个元素都是 0。这可能没问题，因为调用者可以检查它，但 return 可能更好null，特别是因为 0 是在其中一个中返回的有效值元素。

聚苯乙烯。在考虑了更多之后，一旦对数组进行了排序，就不需要进行二进制搜索来获得答案；您应该能够在 O(N) 时间内完成，方法是让一个索引在数组中前进，另一个索引后退。此外，当您排序时，您可能希望创建一些包含值和原始索引的小对象arr，并对它们进行排序，以便您可以将原始索引放入返回数组中。或者只搜索arr您找到的两个值，即 O(N)。

于 2013-08-30T02:05:43.107 回答
0

  1. 是的，我将从对数组进行排序开始。

  2. 但在那之后，我将只使用二叉树来查找第一个（现在是当前）元素的对。

  3. 即使当前元素没有正确的对，我也会记得我在哪里寻找它。

  4. 对于下一个元素，我会从记住的地方开始寻找对，向后。

  5. 返回到 2，直到所看对的索引相遇。

于 2013-08-30T09:03:41.733 回答