查找数组中的MIN MAX对

Question

给定一个有N个整数的排序数组，我需要找到具有不同索引(i!=j)的所有对。我需要(j>i)中所有配对中的最大值(a[j]+a[i]-1)和最小值(a[j]-a[i]+1)。数字不是唯一的，但它们的配对是允许的。数字不能与自己配对。

我在做什么现在：

for(i=0;i<n;i++) 
{ 
    for(j=i+1;j<n;j++) 
    { 
     MAX= max(MAX,a[j] + a[i] -1); 
     MIN=min(MIN,a[j]-a[i]+1); 
    } 
} 

这给Ø的时间复杂度（N^2）。有没有办法将它减少到O（nlogn）甚至更少？

Answer 1

要找到max您只需要添加索引为n-1和n-2的元素，因为数组已经排序并且最大的2个元素将仅位于数组的末尾。数组中没有其他元素会比这些元素大，因此它们的总和也会大于任何其他元素的总和。

MAX = a[n-1] + a[n-2] - 1; 

时间复杂度：O（1）

为了寻找分钟，你应该寻找数组中的支点。我选择从[0]开始。如果空间不是约束，则创建另一个具有相似大小的数组，并使用数据透视表中的增量值填充它。

int[] b = new int[n]; 
for(int i=1; i<n; i++) 
{ 
    b[i] = a[i] - a[0]; 
} 

现在第二个数组将具有来自枢轴的增量值。所有你必须找到的是数组b的最小值和次最小值的索引。这两个值将是最接近每个值的值，因此它们的差异也是最小的。

时间复杂度：为O（n）+ O（n）的= O（N）

空间复杂：O（n）的作为相同大小的新阵列具有被创建。