AC牛客 BM97 旋转数组

简介: AC牛客 BM97 旋转数组

BM97 旋转数组

题目描述

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

数据范围:0<n≤100,0≤m≤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)
AI 代码解读

解题思路

1.此题实际上很简单,如果采用辅助数组的话,那么只需要去平移就可以了
2.但是题目要求空间复杂度为O(1),所以我们要考虑原地移动,那么明显需要找寻一下规律
3.步骤

  • step 1:因为m可能大于n,因此需要对n取余,因为每次长度为n的旋转数组相当于没有变化。
  • step 2:第一次将整个数组翻转,得到数组的逆序,它已经满足了右移的整体出现在了左边。
  • step 3:第二次就将左边的m个元素单独翻转,因为它虽然移到了左边,但是逆序了。
  • step 4:第三次就将右边的n−m个元素单独翻转,因此这部分也逆序了。

实践代码

import java.security.spec.ECPrivateKeySpec;
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) {
        reverseA(a, 0, n - 1);
        reverseA(a, 0, m % n - 1);
        reverseA(a, m % n, n - 1);
        return a;
    }

    private void reverseA(int[] a, int i, int j) {
        while (i < j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }

}
AI 代码解读
目录
打赏
0
0
0
0
30
分享
相关文章
剑指offer(C++)-JZ51:数组中的逆序对(算法-排序)
剑指offer(C++)-JZ51:数组中的逆序对(算法-排序)
|
10月前
【题解】NowCoder BC153 [NOIP2010]数字统计
【题解】NowCoder BC153 [NOIP2010]数字统计
41 6
剑指offer JZ37数字在排序数组中出现的次数
剑指offer JZ37数字在排序数组中出现的次数
67 0
AC牛客 BM99 顺时针旋转矩阵
AC牛客 BM99 顺时针旋转矩阵
111 0
AC牛客 BM99 顺时针旋转矩阵
AC牛客 BM4 合并两个排序的链表
AC牛客 BM4 合并两个排序的链表
112 0
AC牛客 BM4 合并两个排序的链表