NC110 旋转数组

发表于 分类于 ， ， Waline： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

NC110 旋转数组

描述

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 $M$（ $M>=0$）个位置，即将A中的数据由
$$
A_0 , A_1, \cdots , A_{N-1}
$$

变换为
$$
A_{N-M},\cdots,A_{N-1},A_0,A_1,\cdots ,A_{N-M-1}
$$

（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

数据范围：$0<n \leq 10$，$0 \leq m \leq 1000$
进阶：空间复杂度 $O(1)$，时间复杂度 $O(n)$

示例1

输入：

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

返回值：

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

示例2

输入：

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

返回值：

1
[1,2,3,4]

备注：

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

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;

public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        int temp;
        // 每次循环可以把数组最后一个元素循环移动到数组的第一个元素
        // 循环m次即可把数组循环右移m个位置
        for (int j = 0; j < m; j++) {
            // 缓存最后一个元素
            temp = a[a.length - 1];
            // 从后向前遍历
            for (int i = a.length - 1; i > 0; i--) {
                // 把前一格元素移动到后一格
                a[i] = a[i - 1];
            }
            // 把最后一个元素放到第一格
            a[0] = temp;
        }
        return a;
    }
}

根据题目可以值n就是数组的长度，所以可以把上面的a.length替换成n：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        int temp;
        for (int j = 0; j < m; j++) {
            // 缓存最后一个元素
            temp = a[n - 1];
            // 从后向前遍历
            for (int i = n - 1; i > 0; i--) {
                // 把前一格元素移动到后一格
                a[i] = a[i - 1];
            }
            // 把最后一个元素放到第一格
            a[0] = temp;
        }
        return a;
    }
}

大神题解

三次翻转
假设 n=7且 k=3

描述 数组状态
原始数组 1 2 3 4 5 6 7
反转所有数字后 7 6 5 4 3 2 1
反转前 k=3 个数字后 5 6 7_4 3 2 1
反转后 n-k=4 个数字后 5 6 7_1 2 3 4 –> 结果 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
public class Solution {
    public int[] solve (int n, int m, int[] a) {
        int k=m%n;
        reverse(a,0,n-1);
        reverse(a,0,k-1);
        reverse(a,k,n-1);
        return a;
    }
    
    public void reverse(int[] a,int start,int end){
        while (start<end){
            int temp=a[start];
            a[start]=a[end];
            a[end]=temp;
            start++;
            end--;
        }
    }
}

数组翻转

链接：https://www.nowcoder.com/questionTerminal/e19927a8fd5d477794dac67096862042?answerType=1&f=discussion
来源：牛客网

解题思路：

该方法基于如下的事实：将数组的元素向右移动 k 次后，尾部 m mod n 个元素会移动至数组头部，其余元素向后移动 m mod n 个位置。
该方法为数组的翻转：翻转算法参考 反转链表中的双指针方法 https://blog.nowcoder.net/n/d259b250747b4085bc7975f102d248c4

1、可以先将所有元素翻转，这样尾部的 m mod n 个元素就被移至数组头部，

2、然后再翻转 [0,m mod n−1] 区间的元素

3、 最后翻转[m mod n,n−1] 区间的元素即能得到最后的答案。

实例：
以 n=7，m=3 为例进行如下展示：

操作 结果
原始数据 【1，2，3，4，5，6，7】
翻转所有元素 【7，6，5，4，3，2，1】
翻转 [0,m mod n −1] 区间的元素 【5，6，7，4，3，2，1】
翻转 [m mod n, n −1] 区间的元素 【5，6，7，1，2，3，4】

最后返回：【5，6，7，1，2，3，4】

复杂度分析

时间复杂度：O(N)，其中 N 为数组的长度。每个元素被翻转两次，一共 N 个元素，因此总时间复杂度为 O(2N)=O(N)。
空间复杂度：O(1)。使用常数级空间变量