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
分享
相关文章
poj 1503 高精度加法
把输入的数加起来,输入0表示结束。 先看我Java代码,用BigINteger类很多东西都不需要考虑,比如前导0什么的,很方便。不过java效率低点,平均用时600ms,C/C++可以0ms过。
64 1
|
11月前
Pseudoprime numbers(POJ-3641 快速幂)
Pseudoprime numbers(POJ-3641 快速幂)
poj 1990 MooFest 树状数组
题意就是有N头牛,每头牛都有一个坐标和声调值(x, v),两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值,现在要任意两头牛之间都相互通讯一次,求总共需要花费多少能量?
62 0
Bellman-Ford算法求最短路和负环
Bellman-Ford算法求最短路和负环
108 0
Bellman-Ford算法求最短路和负环
棋盘问题 POJ 1321
总时间限制:  1000ms 内存限制:  65536kB 描述 在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
1203 0
POJ 1067 取石子游戏
取石子游戏 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 40917   Accepted: 13826 Description 有两堆石子,数量任意,可以不同。
1136 0
poj supermaket (贪心)
http://poj.org/problem?id=1456 #include #include #include using namespace std; struct nod { int a; int d; }; bool cmp(nod x,nod y) { return x.
711 0