c++ - 从数组中查找 MIN MAX 对

Question

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

我现在在做什么:

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);
    }
}

这给出了 O(n^2) 的时间复杂度。有没有办法将它减少到 O(nlogn) 甚至更少？

Answer 1

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

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

时间复杂度:O(1)

要找到 min ，您应该在数组中查找 pivot。我选择从a[0]开始。如果空间不是约束，请创建另一个大小相似的数组，并使用数据透视表中的增量值填充它。

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

现在第二个数组将具有来自您的数据透视表的增量值。您只需找到数组 b 的最小值和下一个最小值的索引。这 2 个将是最接近的值，因此它们的差异也将是最小的。

时间复杂度:O(n) + O(n) = O(n)

空间复杂度:O(n)，因为必须创建一个相同大小的新数组。