有没有办法使用单个循环比较数组中的每个元素？

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 _我 ≤N：O（n）的

由于每一个X _我也认为1≤x _我 ≤N，它认为，由于鸽巢原理，或者所有值恰好存在一次，或值存在两次或更多次。

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

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

// 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 ⁿ的情况下，它将返回1，而在其他情况下，它将返回0，因此随机输入的平均值为n！/ n ⁿ。随着n的增大，不存在“冲突”的可能性变得很小，因此，正如@YvesDaoust所说，近似的0可能性很大。

如果没有1≤x _我 ≤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;
}