有什么方法可以使用单个循环比较数组中的每个元素吗？

Question

我需要打印 int 数组中任意两个元素之间的最小差异。

数组 A 的每个元素都小于等于它的长度。

1 <= A[i] <= A.length;

我在 Java 中尝试了下面给出的方法 - 但是当给定数组大小 ~10^5.

时，这需要超过 1 秒才能找到结果

我认为这可能是一种幼稚的做法。有什么办法可以进一步优化它吗？可以在 O(n) 时间复杂度内完成吗？

static int findResult(int[] arr)
        {
                 int max =  Integer.MAX_VALUE;
                 HashSet<Integer> hs = new HashSet<Integer>();
                 for(int obj : arr)
                 {
                     hs.add(obj);
                 }
                if(hs.size()==1 )
                {
                    return 0;             // if all elements are same
                }
                 for(int i=0; i<arr.length; i++)
                 {  
                     for(int j=i+1; j<arr.length; j++)
                     {
                         int value = Math.abs(a[i]-a[j]);
                         if(value<max)
                         {
                            max = value;
                         }

                      }         
                }
        return max;  // returns the smallest positive difference
    }

Answer 1

与1≤x_i≤n: O(n)

因为对于每个 x_i 它认为 1≤x_i≤n，它认为，由于pigeonhole principle，所有值都恰好存在once，或者一个值存在两次或更多次。

在前一种情况下，差异是1（对于大于1个元素的数组），在后一种情况下，结果是0，自此有两项是完全相等。

因此我们可以遍历数组并跟踪数字。如果一个数已经存在一次，我们return0，否则，我们return1，如：

// only if it holds that for all i, 1 <= arr[i] <= arr.length
static int findResult(int[] arr) {
    bool[] found = new bool[arr.length]
    for(int i = 0; i < arr.length; i++) {
        if(found[arr[i]-1]) {
            return 0;
        } else {
            found[arr[i]-1] = true;
        }
    }
    return 1;
}

满足条件的随机数组有n个元素，在n!/nⁿ 的情况下，它会 return 1，而在其他情况下，它会 return 0，所以随机输入的平均值是 n!/nⁿ。随着 n 变大，没有 "collisions" 的可能性很小，因此，作为，0 的近似值很可能.

没有1≤x_i≤n: O(n log n)

如果我们放弃约束，我们可以先对数组进行排序，在这种情况下，我们迭代连续的元素：

static int findResult(int[] arr) {
    Arrays.sort(arr);
    int dmin = arr[1] - arr[0];
    for(int i = 2; i < arr.length; i++) {
        int d = arr[i] - arr[i-1];
        if(d < dmin) {
            if(d == 0) {
                return 0;
            }
            dmin = d;
        }
    }
    return dmin;
}

Answer 2

我假设 A 是整数，否则条件 1 <= A[i] <= A.len 没有相关性。

然后有一个O(n)使用直方图的解决方案。

声明一个大小为 A.length 的计数器数组；
计算A的元素的重数;
扫描此直方图以找到最接近的非空 bin。

请注意，此解决方案假定仅考虑非零差异。如果零差异很重要，那么 Willem 的答案更好。

Answer 3

（添加到上述答案中）

如果你需要用额外的 O(1) 来做到这一点 space，你可以在输入序列 A 上使用以下技巧：

for a in A[1...n]:        // a is an element in A; A is 1-indexed; 1 <= a <= n
    if M < A[a % M]:
        return 0
    A[a % M] += M
return 1

这里M(>n)是M+n不溢出。这个技巧可以很容易地修改为使用小于 -n 的 M。

注意事项：

需要随机（即 O(1)）访问 A 的元素。
缓存不友好。

有什么方法可以使用单个循环比较数组中的每个元素吗？

Is there any way to compare each element in an array using a single loop?

algorithm

optimization

array-algorithms

与1≤x_i≤n: O(n)

没有1≤x_i≤n: O(n log n)

有什么方法可以使用单个循环比较数组中的每个元素吗？

Is there any way to compare each element in an array using a single loop?

algorithm

optimization

array-algorithms

与1≤xi≤n: O(n)

没有1≤xi≤n: O(n log n)

与1≤x_i≤n: O(n)

没有1≤x_i≤n: O(n log n)