数组倒序

Question

我在尝试用Java反转一个数组的顺序。
使用最少的内存，在O(n)的时间复杂度下，最有效的方法是什么？
不需要用代码回答，伪代码就可以了。
以下是我的思考过程：

  create a new temp array //I think this is a waste of memory, 
                          //but I am not sure if there's a better way
 grab elements from the end of the original array -decrement this variable
 insert element in beginning of temp array -increment this variable
then make the original array point to the temp array? //I am not sure 
            //if I can do this in java; so let's say the 
            //original array is Object[] arr; and the temp array is 
            //Object[] temp. Can I do temp = arr; ?

有没有更好更有效的方法来做这件事，也许不需要使用临时数组？ 最后，假设数组中没有空值，那么一切都能正常工作。 谢谢

编辑：不，这不是作业。

- marcwho

---

这是作业吗？如果是，请标记为作业。 - Aleks G

考虑交换第一个和最后一个项目，然后交换第二个和倒数第二个项目，直到达到列表的一半... 您只需要一个临时变量，仍然只需遍历列表一次？ - Osama Javed

https://dev59.com/KnI95IYBdhLWcg3w1BhN - user800014

你能使用Java库中的Collections.reverseOrder()吗？ - Churk

只需以相反的顺序循环遍历原始数组，并创建一个新的容器来存储新的顺序插入。这是O(n)的时间复杂度。 - Churk

Answer 1

如果它是一个对象数组，那么Collections.reverse(Arrays.asList(array))可以在常数内存和线性时间内完成工作--不需要临时数组。

- Louis Wasserman

---

+1确实，因为楼主现在说这不是作业，所以这个答案很好。 - Ernest Friedman-Hill

喜欢这个解决方案。刚刚确认不需要临时数组，请参见：http://ideone.com/api/embed.js/link/xLLTpl ... 点击“克隆”，然后点击“运行”。 - eddyparkinson

至少在Java 1.6版本中无法工作： System.out.println( X[ 0 ] + " 到 " + X[ X.length - 1 ] ); Collections.reverse( Arrays.asList( X ) ); System.out.println( X[ 0 ] + " 到 " + X[ X.length - 1 ] ); 输出结果为： 2272.6270739116 到 186.704625250768 2272.6270739116 到 186.704625250768 - Jean-Yves

@Jean-Yves：X的类型是什么？我强烈怀疑它不是一个对象数组，而我在我的答案中指定了这是必要的。 - Louis Wasserman

Answer 2

使用单个临时元素。

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

- ArjunShankar

Answer 3

你不需要使用临时数组；只需从数组开头到中间步进，交换i处的元素与array.length-i-1处的元素。务必正确处理中间元素（这不难，但确保做到）。

- Ernest Friedman-Hill

Answer 4

你可以在不需要临时数组的情况下完成它

• 从数组开头（或结尾，无关紧要）循环到数组中间
• 交换元素和（最后一个元素-索引）处的元素（因此0和size-1，1和size-2等）
• 你会像这样交换:

    temp = a[i];
    a[i] = a[end-i];
    a[end-i] = temp;

• 重复

- twain249

Answer 5

这里有两个解决方案：

    loop to N/2
      swap each element at i with element at N - i

另一个解决方案是（根据您的情况）通过索引来伪造反转数组：

    GetValueAt(int i){return array[N - i];}

- SirGuy

Answer 6

假设我们有一个整数数组arr[] - 整数数组。

for(int i=0,int J=arr.length-1 ; i<j ; i++,j--)
{
    temp =a[i];
    a[i]=a[j];
    a[j]=temp;
 }

这个算法的时间复杂度为O(n/2)，因为我们将执行n/2次交换。它的空间复杂度是常数1，因为我们只使用了一个临时变量。

- Andy

Answer 7

伪代码，假定数组是基于0索引的：

for i in range(0, len(array)/2):
     swap(array[i], array[(len(array)-1)-i])

- mcfinnigan

---

这不像是Java。 - ceving

Answer 8

你只需要两步就可以完成这个操作

ArrayList<Element> YourTempElement= new ArrayList<Element>(mElements);
Collections.reverse(YourTempElement);

- Darshan

---

使用与被接受答案相同的方法，只是不够优雅并且解释较少。 - Nathan Tuggy

不需要解释，这只是一个简单的两步操作，我不是解释者。 - Darshan

在 Stack Overflow 上，好的答案会解释事情。被采纳的答案会这样做。如果已经有一个说了你想说的同样的好答案，或者根本没有办法写出一个好答案，那么添加一个答案到问题中就没有真正的意义：那只会增加噪音。 - Nathan Tuggy