原地反转数组

Question

为什么这个函数reverseArrayInPlace不起作用呢？

我想简单地按照函数的要求来做，即将元素的顺序反转，使结果保存在同一个数组arr中。我选择在函数中使用两个数组来实现这个目标。到目前为止，它只是按照原始顺序返回元素...

    var arr = ["a","b","c","d","e","f"]
    var arr2 = []

    var reverseArrayInPlace = function(array){

      var arrLength = array.length
      for (i = 0; i < arrLength; i++) {
        arr2.push(array.pop())
        array.push(arr2.shift())
      }
    }

    reverseArrayInPlace(arr)

- Sefton419

---

另外，JavaScript 已经具备了内置的原地数组反转功能。 - chiliNUT

正在进行一个数组练习，规定我不能使用那些方法。我正在尝试使用 push、pop、shift 和 unshift 函数。 - Sefton419

https://en.wikipedia.org/wiki/In-place_algorithm - user2844991

@chiliNUT 引用是按值传递的，所以它实际上是有效的。 - Andrea Casaccia

Answer 1

这是一个更简单的反转数组的方法，使用原地算法。

function reverse (array) {
  var i = 0,
      n = array.length,
      middle = Math.floor(n / 2),
      temp = null;

  for (; i < middle; i += 1) {
     temp = array[i];
     array[i] = array[n - 1 - i];
     array[n - 1 - i] = temp;
  }
}

你将数组“分割”成两半。实际上并没有真正地分割，只是遍历了前一半。然后，使用公式n - 1 - i找到相对于中间位置对称的索引，其中i是当前索引。然后使用一个临时变量交换元素。 这个公式是正确的，因为它会交换：

0 <-> n - 1
1 <-> n - 2

等等。如果元素数量是奇数，则中间位置不会受到影响。

- user2844991

Answer 2

pop()会移除数组的最后一个元素，而push()会将一个项添加到数组的末尾。所以你正在重复地弹出和推入数组的最后一个元素。

与其使用push，你可以使用splice，它允许你在数组的特定位置插入一个项：

var reverseArrayInPlace = function (array) {
    var arrLength = array.length;
    for (i = 0; i < arrLength; i++) {
        array.splice(i, 0, array.pop());
    }
}

（请注意，您不需要使用中间数组来完成这个操作。使用中间数组实际上并不是原地反转。只需在当前索引处弹出并插入即可。）

另外，有趣的评论——由于第一个元素始终会在经过 length - 1 次迭代后最终位于最后位置，所以可以跳过最后一次迭代。因此，可以安全地迭代 arrLength - 1 次。

我还想补充一点，JavaScript 中有一个内置的 reverse() 方法可以用于数组。所以 ["a", "b", "c"].reverse() 将得到 ["c", "b", "a"]。

一个真正的原地算法将在数组的中间位置与另一侧对应的元素进行交换，直到达到中间位置为止。

var reverseArrayInPlace = function (array) {
    var arrLength = array.length;
    for (var i = 0; i < arrLength/2; i++) {
        var temp = array[i];
        array[i] = array[arrLength - 1 - i];
        array[arrLength - 1 - i] = temp;
    }
}

- Purag

---

如果我使用相同的push pop，push pop方法，我可以理解你的意思，但我使用的是push pop，push，shift。此外，我已经尝试将shift切换为pop，但最终仍然得到arr = ["a"，"b"，"c"，"d"，"e"，"f"，]。 - Sefton419

任何 push, pop, shift, 和 unshift 的组合只是按顺序移动元素。对于 [a, b, c]，想象多次弹出和移动；你得到 [c, a, b]，然后是 [b, c, a]，最后是 [a, b, c]。所以你什么也没做到数组。 - Purag

嘿，@AustinSefton，我的解释讲得通吗？你明白为什么你的代码不起作用了，对吧？ - Purag

Answer 3

如果你正在做《JavaScript编程精解》，练习明确说明不要使用新数组来进行临时值存储。书后的提示展示了解决方案的结构，类似于Stefan Baiu的答案。

我在这里发布的答案比Stefan的代码行数少，因为我认为在函数内部将array.length之类的值存储在变量中是多余的。这样做也更容易阅读，适合我们初学者。

function reverseArrayInPlace(array) {

    for (var z = 0; z < Math.floor(array.length / 2); z++) {
        var temp = array[z];
        array[z] = array[array.length-1-z];
        array[array.length-1-z] = temp;
    }
    return array;
}

- Joolian

---

这里没有叫"Stefan Baiu"的人。它指的是什么答案？ - Peter Mortensen

Answer 4

我觉得你想要一个简单的方法来反转一个数组。

var yourArray = ["first", "second", "third", "...", "etc"]
var reverseArray = yourArray.slice().reverse()

console.log(reverseArray)

你会得到

["etc", "...", "third", "second", "first"]

- Kangudie Muanza - Killmonger

---

不，那是一个设定的限制（尽管它不应该出现在评论中）：“JavaScript已经内置了一个原地数组反转... [我]正在进行一个数组练习，规定我不能使用那些方法。我正在尝试使用push、pop、shift和unshift函数来解决问题。” - Peter Mortensen

Answer 5

您正在使用arr作为参数调用该函数，因此函数内部arr和array都指向同一个数组。这意味着代码执行的与以下代码相同：

var arr = ["a","b","c","d","e","f"]
var arr2 = []

var arrLength = arr.length;
for (i = 0; i < arrLength; i++) {
  arr2.push(arr.pop())
  arr.push(arr2.shift())
}

这些语句从arr中获取最后一个项目并将其放到arr2的最后。现在你有：

arr = ["a","b","c","d","e"]
arr2 = ["f"]

第二个语句从arr2中获取第一个（也是唯一的）项目，并将其放在arr的最后一个位置：

arr = ["a","b","c","d","e","f"]
arr2 = []

现在你回到了起点，对于循环中的所有迭代都是如此。最终结果是什么也没改变。

---

为了使用pop和push将项目反向放置在另一个数组中，您只需移动项目直到该数组为空即可。

while (arr.length > 0) {
  arr2.push(arr.pop());
}

如果你想把它们移回去（而不仅仅使用新数组），你可以使用 shift 来获取 arr2 开头的项目，然后使用 push 把它们放到 arr 的末尾：

while (arr2.length > 0) {
  arr.push(arr2.shift());
}

---

通常情况下，使用栈/队列操作不会执行原地反转，只需将开头的项与结尾的项交换即可。这样做更快，而且不需要另一个数组作为缓冲区：

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

这将交换成对的内容，如下所示：

["a","b","c","d","e"]
  |   |       |   |
  |   +-------+   |
  +---------------+

- Guffa

---

为了避免最后一个 while 循环，您也可以先执行 arr2=arr.splice(0,n)，然后将角色颠倒过来进行第一个 while 循环：while(arr2.length)arr.push(arr2.pop())。 - Carsten Massmann

@cars10：重点是展示如何使用栈/队列操作，就像OP尝试的那样。当然，有几种更简单的方法可以做到这一点。 - Guffa

Answer 6

这是我的解决方案，没有使用任何临时数组。它并不是什么突破性的东西，只是一些提议解决方案的简化版本。

let array = [1, 2, 3, 4, 5];

 for(let i = 0; i<Math.floor((array.length)/2); i++){
     var pointer = array[i];
     array[i] = array[ (array.length-1) - i];
     array[(array.length-1) - i] = pointer;
 }

 console.log(array);
 //[ 5, 4, 3, 2, 1 ]

- oKonyk

Answer 7

这与批准的答案类似，但我使用数组解构而不是临时变量来交换数组中的元素。

const reverseArrayInPlace = array => {
  for (let i = 0; i < array.length / 2; i++) {
   [array[i], array[array.length - 1 - i]] = [array[array.length - 1 - i], array[i]]
 }
  return array
}

const myArray = [1,2,3,4,5,6,7,8,9];
console.log(reverseArrayInPlace(myArray))

- Scott Price

Answer 8

在我为这个任务设定的限制下，这是我解决问题的方法：

var arr = ["a","b","c","d","e","f"]
var arr2 = []

var reverseArrayInPlace = function(array){

      var arrLength = array.length
      for (i = 0; i < arrLength; i++) {
        arr2.push(array.pop())
      }
      for (i = 0; i < arrLength; i++) {
        array[i] = arr2.shift()
      }
    }

      reverseArrayInPlace(arr)

谢谢你的所有帮助！

为所有对此仍有兴趣的人，我使用了这个线程和我自己的思维设备的一些帮助来重写它...目前我的思维能力有限。这是它：

    arr = [1,2,3,4,5,6,7,8,9,10,11,12,13]
    arr2 = ["a","b","c","d","e","f"]
    arr3 = [1,2,3]
    arr4 = [1,2,3,4]
    arr5 = [1,2,3,4,5]


    var reverseArrayInPlace2 = function(array) {

      var arrLength = array.length
      var n = arrLength - 1
      var i = 0
      var middleTop = Math.ceil(arrLength/2)
      var middleBottom = Math.floor(arrLength/2)

      while (i < Math.floor(arrLength/2)) {

        array[-1] = array[i]
        array[i] = array[n]
        array[n] = array[-1]
        // console.log(array)
        i++
        n--

      }

      return array
    }

    console.log(reverseArrayInPlace2(arr))
    console.log(reverseArrayInPlace2(arr2))
    console.log(reverseArrayInPlace2(arr3))
    console.log(reverseArrayInPlace2(arr4))
    console.log(reverseArrayInPlace2(arr5))

P.S. 改变全局变量有什么问题？有什么替代方案吗？

- Sefton419

---

我不确定它是否真正算作“原地”，但我很高兴你解决了你的问题。 - user2844991

通常不建议在函数中更改全局变量（在您的情况下为arr2）。请阅读@Guffa在他的答案中写的内容。他解释得非常好！ - Carsten Massmann

我对三种主要方法（JS内置、pop/push和原地交换）在速度上的差异感到惊讶，详情请参见此处：http：//jsperf.com/reverse-builtin-vs-optimised#run - Carsten Massmann

谢谢@cars10，我明白你的意思了。以后我会避免这种情况的发生。 - Sefton419

改变全局变量有什么问题吗？您可能会在不同的位置应用该函数。如果您实际上依赖于首次使用更改的全局变量，那么在随后的调用中更改它可能会导致非常混乱的行为。这种“副作用”对于期望仅在原地更改数组的毫无戒备的用户来说根本不透明。替代方法应该是使用局部变量（在函数内部声明），并且 - 如果您真的想要返回该变量 - 将其附加到返回的对象或数组作为属性。 - Carsten Massmann

Answer 9

此解决方案使用了对while的简写。

var arr = ["a","b","c","d","e","f"]

const reverseInPlace = (array) => {
  let end = array.length;
  
  while(end--)
    array.unshift(array.pop());
    
  return array;
}

reverseInPlace(arr)

- techmsi

---

这只是在循环遍历数组，最终返回相同的数组。 - Aaron

为什么开头和结尾的格式这么奇怪？意图是什么？ - Peter Mortensen

Answer 10

function reverseArrayInPlace (arr) {
  var tempArr = [];
  for (var i = 0; i < arr.length; i++) {
    // Temporarily store last element of original array
    var holdingPot = arr.pop();
    // Add last element into tempArr from the back
    tempArr.push(holdingPot);
    // Add back value popped off from the front
    //  to keep the same arr.length
    //  which ensures we loop thru original arr length
    arr.unshift(holdingPot);
  }
  // Assign arr with tempArr value which is the reversed
  //  array of the original array
  arr = tempArr;
  return arr;
}

- HeggyHere