好的,我知道通过交换数组项直到达到中间来反转一个数组非常容易。像这样:
int array[SIZE];
int temp;
for (int i = 0; i < SIZE/2; i++)
{
temp = array[i];
array[i] = array[SIZE-1 - i];
array[SIZE-1 - i] = temp;
}
但是如果数组的大小非常大,比如10000,是否有可能以O(N)的时间复杂度进行操作?
public class ReversableArray {
private boolean reverse = false;
private final int[] array;
public ReversableArray(int[] array) { this.array = array; }
public int get(int index) {
return reverse ? array[array.length - index - 1] : array[index];
}
public void reverse() { reverse = !reverse; }
}
反转一个数组的时间复杂度不能比O(n)更快。然而,你的代码的时间复杂度也是O(n)。
大O符号的定义:
不是无限大
或者我们可以说:
存在一个常数c,使得c.f(x)大于g(x)对于所有x的值。
在这里,我们考虑n是我们数组的大小,函数T(n)是我们程序的步骤。
交换两个整数的成本是恒定的时间。进行n/2次交换将导致O(n)。
很抱歉没有在答案中包含图像。
com.google.common.collect.Lists.reverse
已经实现了这一点。 - cpp beginnerArrayUtils.reverse(int[]array)
,它能用于字符串数组吗? - Ege Kuzubasioglu