查找數組中的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）的作爲相同大小的新陣列具有被創建。