在 JavaScript 中旋转数组中的元素

IT技术 javascript arrays rotation
2021-01-21 01:49:31

我想知道旋转 JavaScript 数组的最有效方法是什么。

我想出了这个解决方案,其中正数n将数组向右旋转,负数n向左旋转( -length < n < length) :

Array.prototype.rotateRight = function( n ) {
  this.unshift( this.splice( n, this.length ) );
}

然后可以这样使用:

var months = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"];
months.rotate( new Date().getMonth() );

我上面的原始版本有一个缺陷,正如Christoph在下面的评论中指出的那样,正确的版本是(额外的返回允许链接):

Array.prototype.rotateRight = function( n ) {
  this.unshift.apply( this, this.splice( n, this.length ) );
  return this;
}

是否有更紧凑和/或更快的解决方案,可能在 JavaScript 框架的上下文中?(以下建议的版本都不是更紧凑或更快)

有没有内置数组旋转的 JavaScript 框架?(仍然没有人回答)

6个回答

您可以使用push()pop()shift()unshift()方法:

function arrayRotate(arr, reverse) {
  if (reverse) arr.unshift(arr.pop());
  else arr.push(arr.shift());
  return arr;
}

用法:

arrayRotate([1, 2, 3, 4, 5]);       // [2, 3, 4, 5, 1];
arrayRotate([1, 2, 3, 4, 5], true); // [5, 1, 2, 3, 4];

如果您需要count争论,请参阅我的另一个答案:
https: //stackoverflow.com/a/33451102 🖤🧡💚💙💜

它没有计数,尽管根据用途这不是什么大问题。
2021-03-11 01:49:31
请注意:请注意此方法是侵入性的,它将操纵作为参数发送的数组。不难解决在发送之前复制数组
2021-03-19 01:49:31
这是typescript中的一个版本,带有左右变量stackblitz.com/edit/typescript-vtcmhp
2021-03-21 01:49:31
@JustGage,我发布了另一个支持计数的答案stackoverflow.com/questions/1985260/...
2021-04-07 01:49:31

类型安全的通用版本,它改变了数组:

Array.prototype.rotate = (function() {
    // save references to array functions to make lookup faster
    var push = Array.prototype.push,
        splice = Array.prototype.splice;

    return function(count) {
        var len = this.length >>> 0, // convert to uint
            count = count >> 0; // convert to int

        // convert count to value in range [0, len)
        count = ((count % len) + len) % len;

        // use splice.call() instead of this.splice() to make function generic
        push.apply(this, splice.call(this, 0, count));
        return this;
    };
})();

在评论中,Jean 提出了代码不支持push()重载的问题splice()我不认为这真的很有用(见评论),但一个快速的解决方案(虽然有点黑客)将替换该行

push.apply(this, splice.call(this, 0, count));

有了这个:

(this.push || push).apply(this, (this.splice || splice).call(this, 0, count));

在 Opera 10 中使用unshift()代替的push()速度几乎快两倍,而在 FF 中的差异可以忽略不计;代码:

Array.prototype.rotate = (function() {
    var unshift = Array.prototype.unshift,
        splice = Array.prototype.splice;

    return function(count) {
        var len = this.length >>> 0,
            count = count >> 0;

        unshift.apply(this, splice.call(this, count % len, len));
        return this;
    };
})();
@Jean:好吧,闭包捕获了整个作用域链;只要外部函数是顶级的,影响应该可以忽略不计,无论如何都是 O(1),而查找 Array 方法的调用次数是 O(n);优化实现可能会内联查找,因此不会有任何收益,但是对于我们不得不处理很长时间的相当愚蠢的解释器,在较低范围内缓存变量可能会产生重大影响
2021-03-14 01:49:31
这里的闭包成本是多少,只是为了缓存推送和拼接?
2021-03-16 01:49:31
很好的Array.prototype方法缓存+1
2021-03-25 01:49:31
这不会旋转大型阵列。我今天检查了一下,它只能处理长度为 250891 项的数组。显然,您可以通过apply方法传递的参数数量受到特定调用堆栈大小的限制。在 ES6 术语中,扩展运算符也会遇到相同的堆栈大小问题。下面我给出了一个做同样事情的地图方法。它较慢,但适用于数百万个项目。您还可以使用简单的 for 或 while 循环来实现 map,它会变得更快。
2021-03-26 01:49:31
非常好的防弹实现,但总的来说,我更愿意依赖异常,或者只是简单的错误响应,用于不良使用。这是为了保持代码干净和快速。用户有责任传递正确的参数或承担后果。我不喜欢对好用户的惩罚。除此之外,这是完美的,因为它确实根据要求修改了数组,并且它没有受到我的实现中的缺陷的影响,即未移动数组而不是您指出的单个元素。返回 this 也更好地允许链接。那谢谢啦。
2021-04-01 01:49:31

我可能会做这样的事情:

Array.prototype.rotate = function(n) {
    n = n % this.length;
    return this.slice(n, this.length).concat(this.slice(0, n));
}

编辑    这是一个mutator版本:

Array.prototype.rotate = function(n) {
    n = n % this.length;
    while (this.length && n < 0) n += this.length;
    this.push.apply(this, this.splice(0, n));
    return this;
}
它需要修改原来的Array(this),就像push、pop、shift、unshift、concat、splice一样。除此之外,这是有效的。
2021-03-21 01:49:31
请记住,此函数保持原始数组不变
2021-03-24 01:49:31
@Gumbo,为什么是 while 循环?我们不需要使 n 为正,拼接也适用于负值。最后,这是正确的,但几乎是 Christoph 版本,它在没有过载警告的情况下首先正确。
2021-03-25 01:49:31
n = n % this.length在 return 语句之前添加了处理负数和/或超出边界的数字。
2021-04-06 01:49:31
@Gumbo,更正我之前的评论,负数仅适用于 splice( n. this.length ) 版本。在您的版本中使用 splice( 0, n ) 需要正整数。
2021-04-08 01:49:31

此函数以两种方式工作,并适用于任何数字(即使数字大于数组长度):

function arrayRotate(arr, count) {
  count -= arr.length * Math.floor(count / arr.length);
  arr.push.apply(arr, arr.splice(0, count));
  return arr;
}

用法:

for(let i = -6 ; i <= 6 ; i++) {
  console.log(arrayRotate(["🧡","💚","💙","💜","🖤"], i), i);
}

结果:

[ "🖤", "🧡", "💚", "💙", "💜" ]    -6
[ "🧡", "💚", "💙", "💜", "🖤" ]    -5
[ "💚", "💙", "💜", "🖤", "🧡" ]    -4
[ "💙", "💜", "🖤", "🧡", "💚" ]    -3
[ "💜", "🖤", "🧡", "💚", "💙" ]    -2
[ "🖤", "🧡", "💚", "💙", "💜" ]    -1
[ "🧡", "💚", "💙", "💜", "🖤" ]    0
[ "💚", "💙", "💜", "🖤", "🧡" ]    1
[ "💙", "💜", "🖤", "🧡", "💚" ]    2
[ "💜", "🖤", "🧡", "💚", "💙" ]    3
[ "🖤", "🧡", "💚", "💙", "💜" ]    4
[ "🧡", "💚", "💙", "💜", "🖤" ]    5
[ "💚", "💙", "💜", "🖤", "🧡" ]    6
使用这个函数我遇到了一个问题,因为它改变了原始数组。我在这里找到了一些解决方法:stackoverflow.com/questions/14491405
2021-03-15 01:49:31
@Hybridwebdev 使用 const immutatableArrayRotate = (arr, count) => ArrayRotate(arr.clone(), count)
2021-03-24 01:49:31
@ognockocaten 这不是问题,而是此功能的工作方式。如果您想保持原始数组不变,请先克隆它:var arr2 = arrayRotate(arr.slice(0), 5)
2021-04-08 01:49:31
这确实是一个很好的答案,它帮助了我。但是,最好提供一种不会改变原始数组的替代方法。当然,仅仅创建原始副本很容易,这不是最佳实践,因为它不必要地使用内存。
2021-04-08 01:49:31

许多这些答案似乎过于复杂且难以阅读。我想我没有看到有人使用带有 concat 的 splice ...

function rotateCalendar(){
    var cal=["Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"],
    cal=cal.concat(cal.splice(0,new Date().getMonth()));
    console.log(cal);  // return cal;
}

console.log 输出(* 于 5 月生成):

["May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec", "Jan", "Feb", "Mar", "Apr"]

至于紧凑性,我可以提供几个通用的单行函数(不包括 console.log | return 部分)。只需将数组和参数中的目标值提供给它即可。

我将这些函数合并为一个四人纸牌游戏程序,其中数组为 ['N','E','S','W']。我将它们分开,以防有人想根据需要复制/粘贴。出于我的目的,我在游戏的不同阶段(Pinochle)寻找下一个轮到谁玩/行动时使用这些功能。我没有费心测试速度,所以如果其他人愿意,请随时让我知道结果。

*注意,功能之间的唯一区别是“+1”。

function rotateToFirst(arr,val){  // val is Trump Declarer's seat, first to play
    arr=arr.concat(arr.splice(0,arr.indexOf(val)));
    console.log(arr); // return arr;
}
function rotateToLast(arr,val){  // val is Dealer's seat, last to bid
    arr=arr.concat(arr.splice(0,arr.indexOf(val)+1));
    console.log(arr); // return arr;
}

组合功能...

function rotateArray(arr,val,pos){
    // set pos to 0 if moving val to first position, or 1 for last position
    arr=arr.concat(arr.splice(0,arr.indexOf(val)+pos));
    return arr;
}
var adjustedArray=rotateArray(['N','E','S','W'],'S',1);

调整数组=

W,N,E,S
@Wes你针锋相对达我的回答的批评没有提供理由为什么concatsplice()不应使用。这似乎是一个自我推销的评论,它将研究人员从一个赞成的答案引导到一个不赞成的答案。当您有吹哨的理由时,您应该将其包含在您的举报评论中。你的新答案没有试图解释自己,也没有试图解释为什么我的答案中的技术应该被避免。对于所问的问题,我认为 concat&splice 没有任何问题 - 独特月份的数组,旋转到前面。
2021-03-11 01:49:31
这些函数看起来是嵌套的,但它们的返回值只传递给父函数一次。所以,是的,即使它们有很大的 O 时间复杂度n,它们也不会以嵌套的方式迭代。这意味着这O(n ^ 2)是一个错误的断言。如果这三个函数都是O(n),那么总的最坏情况是O(n + n + n)更有吸引力的是,时间复杂度很小o(1 + 1 + 1)——这可能有条件地优于对每个单个元素(o(n)O(n)执行条件评估的映射/循环技术我的答案没有迭代条件。
2021-04-01 01:49:31
我的答案已经更新,有更详细的解释。我在你删除反对票之前发表了上述评论,现在我将删除它,因为你纠正了这个问题。有关 concat 和 splice 的完整说明,请参阅我的解决方案。简而言之,他们做了很多工作,每个工作都返回一个新数组。此外, .indexOf 方法是 O(n) 线性搜索。因此,在 splice 内部使用(在 concat 内部使用),您的时间复杂度接近 O(n^2)。当你的代码都靠得很近的时候,阅读你的代码也真的很困难,因为它的value。只是我脑子里的一些想法。
2021-04-02 01:49:31
:) 顺便说一句,我在这里用过
2021-04-06 01:49:31