首页 > 试题广场 >

旋转数组

[编程题]旋转数组

热度指数：53983 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A₀ A₁ ……A_N-1 ）变换为（A_N-M …… A_N-1 A₀ A₁ ……A_N-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

数据范围： $0 < n \le 100$ ， $0 \le m \le 1000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

6,2,[1,2,3,4,5,6]

输出

[5,6,1,2,3,4]

示例2

输入

4,0,[1,2,3,4]

输出

[1,2,3,4]

备注:

(1<=N<=100,M>=0)

算法知识视频讲解

JavaScript Node

bravefei

function solve(n, m, a) {

// write code here

// 使用数组的切割 + 扩展运算符 + 长度取余

return [...a.slice(n - (m % n), n), ...a.slice(0, n - (m % n))];

}

发表于 2023-03-28 14:14:08 回复(0)

JavaScript Node

Whiskeyi

function solve( n ,  m ,  a ) {
   for (let i = 0; i < m; i++) {
       a.unshift(a.pop())
   }
   return a
}

发表于 2022-11-06 20:55:46 回复(1)

JavaScript Node

petrichor11

function solve( n ,  m ,  a ) {
    if(a.length === 0 || m === 0) return a
    m = n > m? m : m % n
    let res = []
    let j = 0
    for(var i = 0; i < n; i++) {
        if(i < n - m) {
            res[i+m] = a[i]
        } else {
            if(j <= m - 1) {
                res[j] = a[i]
                j++
            }
        }
    }
    return res
}
module.exports = {
    solve : solve
};

发表于 2022-07-06 12:02:25 回复(0)

JavaScript Node

啊哈打工人

注意点：

1. 空间复杂度为O(n)

2. m >= n 的特例，要先取模

reverse 三次

function solve( n ,  m ,  a ) {
    // write code here
    m = m % n
    a = reverse(a, 0, n - 1)
    a = reverse(a, 0, m - 1)
    a = reverse(a, m, n - 1)
    return a
}
function reverse (arr, left, right){
    for(; left < right; left ++, right --){
        [arr[left], arr[right]] = [arr[right], arr[left]]
    }
    return arr
}

发表于 2022-04-14 16:06:08 回复(0)