我需要打印一个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
}
由于每一个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 n的情况下，它将返回1，而在其他情况下，它将返回0，因此随机输入的平均值为n！/ n n。随着n的增大，不存在“冲突”的可能性变得很小，因此，正如@YvesDaoust所说，近似的0可能性很大。
如果我们删除约束，我们可以首先对数组进行排序，在这种情况下，我们遍历连续的元素：
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;
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句