给定一个由 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) 甚至更少?
最佳答案
要找到最大值,您只需添加索引 n-1 和 n-2 处的元素,因为数组已经排序,并且 2 个最大的元素仅位于索引的末尾大批。数组中没有其他元素会比这些元素大,因此它们的总和也将大于任何其他元素的总和。
MAX = a[n-1] + a[n-2] - 1;
时间复杂度:O(1)
要查找 min ,您应该在数组中查找主元。我选择从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),因为必须创建相同大小的新数组。
关于c++ - 从数组中查找 MIN MAX 对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42184090/