如果有一个由N个元素组成的整数数组A,例如{4,2,11,-2,1},我需要从每个子数组中找到具有最大值的元素。子阵列是这样生成的:
for i = 0, leftArray = {4} , rightArry = {2,11,-2,1}
for i = 1, leftArray = {4,2}, rightArry = {11,-2,1}
for i = 2, leftArray = {4,2,11}, rightArry = {-2, 1}
for i = 3, leftArray = {4,2,11,-2}, rightArry {1}
所以,我需要这样的东西:
for (int i = 0; i < A.length; i++){
//LOGIC HERE
System.err.println(String.format("Left array max = %s, Right array max = %s",lmax, rmax));
}
如果我们不关心时间的复杂性,但预计最坏情况下的时间复杂度为O(N)
我不知道如何用O(N)算法来实现这一点。如有任何帮助,我们将不胜感激。
编辑:
我目前的解决方案:
for (int i = 0; i < A.length; i++)
{
if(i == A.length - 1)
break;
int[] l = Arrays.copyOfRange(A, 0, i + 1);
int[] r = Arrays.copyOfRange(A, i + 1, A.length);
Arrays.sort(l);
Arrays.sort(r);
System.err.println(l[l.length -1] + " " + r[r.length - 1]);
}
在O(n)中是可能的,但我只能想如何在两次过程中找到最大值,然后在另一次过程中打印它们:
int[] leftMaxes = new int[A.length - 1];
int[] rightMaxes = new int[A.length - 1];
leftMaxes[0] = A[0];
for (int i = 1; i < A.length - 1; ++i) {
leftMaxes[i] = Math.max(leftMaxes[i-1], A[i]);
}
rightMaxes[A.length - 2] = A[A.length - 1];
for (int i = A.length - 3; i >= 0; --i) {
rightMaxes[i] = Math.max(rightMaxes[i+1], A[i+1]);
}
for (int i = 0; i < A.length - 1; ++i) {
System.out.printf("%d: %d %d%n", i, leftMaxes[i], rightMaxes[i]);
}
Ideone演示
输出:
0: 4 11
1: 4 11
2: 11 1
3: 11 1
您可以组合leftMaxes
和打印循环(先执行rightMaxes
)以删除其中一个循环;但对于所需的复杂性来说,这不是必需的。
您可以将rightMaxes
和leftMaxes
循环组合起来,但我认为这会使代码更难阅读。