一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
数据范围：
，
进阶：空间复杂度 )
，时间复杂度 )
[编程题]旋转数组
1.首先要找出要有效移动的总步骤，m%n，求余就是移动步骤
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) {
// write code here
if(m==0){
return a;
}
int movestep = m % n;
for(int i=0;i<movestep;i++){
int before = a[n-1];
for(int j=n-1;j>0;j--){
a[j] = a[j-1];
}
a[0] = before;
}
return a;
}
}
发表于 2025-02-27 23:39:23
回复(0)
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) {
if(m==0)return a;
int[] res=new int[a.length];
m=m%a.length;
System.arraycopy(a, 0, res, m, a.length-m);
System.arraycopy(a, a.length-m, res, 0, m);
return res;
}
}
发表于 2024-04-22 11:16:29
回复(1)
public int[] solve (int n, int m, int[] a) {
// write code here
m%=n; // 防止n=10 m=11这种情况
reverse(a ,0 ,n-m-1);
reverse(a ,n-m ,n-1);
reverse(a ,0 ,n-1);
return a;
}
public void reverse(int[] arr ,int start ,int end){
while(start<end){
int temp=arr[start];
arr[start++]=arr[end];
arr[end--]=temp;
}
}
编辑于 2024-03-10 15:18:05
回复(0)
public int[] solve (int n, int m, int[] a) {
//截取倒数m个数，放到数组a的最前面
//逆转全部，逆转前m个，逆转后(n-m)个
m=m%n;
reverse(a,0,n-1);
reverse(a,0,m-1);
reverse(a,m,n-1);
return a;
}
public void reverse(int[] a,int begin,int end){
while(begin<=end){
int tmp=a[begin];
a[begin]=a[end];
a[end]=tmp;
//更新指标
begin++;
end--;
}
}
发表于 2023-07-29 11:28:13
回复(0)
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) {
// write code here
int temp = 0;
for(int i = 0; i < m % n; i++){
temp = a[a.length - 1];
for(int j = a.length - 2; j >= 0; j--){
a[j + 1] = a[j];
}
a[0] = temp;
}
return a;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 旋转数组
* @param n int整型 数组长度
* @param m int整型 右移距离
* @param a int整型一维数组 给定数组
* @return int整型一维数组
*/
public int[] solve (int n, int m, int[] a) {
// write code here
int temp = 0;
for(int i = 0; i < m % n; i++){
temp = a[a.length - 1];
for(int j = a.length - 2; j >= 0; j--){
a[j + 1] = a[j];
}
a[0] = temp;
}
return a;
}
}
发表于 2023-07-24 09:11:02
回复(0)
一次就通过了。。。代码非常简单，这确定是mid难度吗？
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) {
// write code here
int mod = m%n;
if(n<=1){
return a;
}
for(int i = 0;i<mod;i++){
romoveOneArray(a);
}
return a;
}
public void romoveOneArray(int[] a){
int len = a.length;
int temp = a[len-1];
for(int i=len-1; i >= 1; i--){
a[i] = a[i-1];
}
a[0] = temp;
}
}
发表于 2023-06-18 23:54:14
回复(0)
看了题解咋都是翻转，直接暴力逐个交换
总思路
从第0个位置开始，将第0个位置的值移入第 (0+m)%n 个位置，需要提前保存下一个位置的值，做 n 次操作。
- 问题一：当 m 是奇数，可以直接按总思路处理。
- 问题二：当 m 是偶数，需要操作两次，因为会 nextIndex 会循环会第一个位置。
- 代码
public int[] solve (int n, int m, int[] a) { // write code here if(a.length <= 1) return a; if(m > n) m = m % n; if(m % 2 == 0) { // 两次 int curIndex = 0; int curValue = a[curIndex]; int nextIndex = (curIndex + m) % n; int nextValue = a[nextIndex]; for(int i=0; i<n/2; i++) { a[nextIndex] = curValue; curIndex = nextIndex; curValue = nextValue; nextIndex = (curIndex + m) % n; nextValue = a[nextIndex]; } curIndex = 1; curValue = a[curIndex]; nextIndex = (curIndex + m) % n; nextValue = a[nextIndex]; for(int i=0; i<n/2; i++) { a[nextIndex] = curValue; curIndex = nextIndex; curValue = nextValue; nextIndex = (curIndex + m) % n; nextValue = a[nextIndex]; } } else { // 一次 int curIndex = 0; int curValue = a[curIndex]; int nextIndex = (curIndex + m) % n; int nextValue = a[nextIndex]; for(int i=0; i<n; i++) { a[nextIndex] = curValue; curIndex = nextIndex; curValue = nextValue; nextIndex = (curIndex + m) % n; nextValue = a[nextIndex]; } } return a; }
发表于 2023-03-25 20:49:43
回复(2)
先把0~(n-m)处的数组翻转，再把(n-m)~n处的数组翻转，最后把整个数组翻转，整个时间复杂度为O（n），空间复杂度为O(1)
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) {
// write code here
m=m%n;
m=n-m;
for(int i=0;i<m/2;i++){
int temp=a[i];
a[i]=a[m-1-i];
a[m-1-i]=temp;
}
for(int i=m;i<(a.length+m)/2;i++){
int temp=a[i];
a[i]=a[a.length-1+m-i];
a[a.length-1+m-i]=temp;
}
for(int i=0;i<a.length/2;i++){
int temp=a[i];
a[i]=a[a.length-1-i];
a[a.length-1-i]=temp;
}
return a;
}
}
发表于 2022-09-16 20:51:17
回复(0)
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) {
// write code here
int temp=0;
for(int t=1;t<=m;t++){
temp=a[n-1];
for(int i=n-2;i>=0;i--){
a[i+1]=a[i];
}
a[0]=temp;
}
return a;
}
}
发表于 2022-08-25 15:25:29
回复(1)
轻轻的我来了
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) {
// write code here
int length = m % n;
reverse(a, 0, n - 1);
reverse(a, 0, length - 1);
reverse(a, length, n - 1);
return a;
}
public void reverse(int[] a, int left, int right) {
while (left < right) {
int temp = a[left];
a[left++] = a[right];
a[right--] = temp;
}
}
}
发表于 2022-08-12 19:44:57
回复(0)
import java.util.*;
public class Solution {
public int[] solve (int n, int m, int[] a) {
m = m % n;
exchange(a, 0, n-1);
exchange(a, 0,m-1);
exchange(a, m,n-1);
return a;
}
public void exchange(int[] a, int start, int end){
while(start < end){
int tmp = a[start];
a[start] = a[end];
a[end] = tmp;
start++;
end--;
}
}
}
发表于 2022-08-07 18:09:11
回复(0)
public class Solution {
/**
* 旋转数组
* @param n int整型 数组长度
* @param m int整型 右移距离
* @param a int整型一维数组 给定数组
* @return int整型一维数组
*/
public int[] solve (int n, int m, int[] a) {
m%=n;
//三次反转
if(m == 0) return a;
reverse(0,n,a);
reverse(0,m,a);
reverse(m,n,a);
return a;
}
public void reverse(int l, int r, int[] a){
while(l<r){
int tmp = a[l];
a[l++]=a[--r];
a[r]=tmp;
}
}
}
发表于 2022-06-22 14:49:56
回复(0)
方法就是三次翻转，确实很经典了
public int[] solve (int n, int m, int[] a) {
if (m % n == 0) return a;
reverse(a, 0, n - 1);
reverse(a, 0, m % n - 1);
reverse(a, m % n, n - 1);
return a;
}
public void reverse(int[] arr, int l, int r) {
while (l < r) {
arr[l] = arr[l] ^ arr[r] ^ (arr[r] = arr[l]); // 使用异或来交换（省行数）
l++; r--;
}
}
发表于 2022-06-15 02:10:44
回复(0)
按m值分批次翻转
此方法比三次翻转的交换次数更少
输入：
6,2,[1,2,3,4,5,6]三次翻转：
反转所有数字 6 5 4 3 2 1 交换3次
反转前m个数 5 6 4 3 2 1 交换1次
反转后n-m个数 5 6 1 2 3 4 交换2次
共交换6次；
分批翻转：
第1批1次： 3 2 1 4 5 6 交换1次
第1批2次： 5 2 1 4 3 6 交换1次
第2批1次： 5 4 1 2 3 6 交换1次
第2批2次： 5 6 1 2 3 4 交换1次
共交换4次；
import java.util.*;
public class Solution {
public int[] solve (int n, int m, int[] a) {
m = m % n;
for (int i = 0; i < m; i++)
for (int j = i + m; j % n != i; j++) {//一次交换后，元素便放置到了正确位置
int tmp = a[i];
a[i] = a[j % n];
a[j % n] = tmp;
}
return a;
}
}
发表于 2022-03-22 14:53:48
回复(2)
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) {
// write code here
m = m % n;//m是移动次数
List<Integer> rest = new ArrayList<Integer>();//用于存放移动时会超出数组的元素
for(int i = n - m ; i < n ; i ++){
rest.add(a[i]);//取出剩余超出的数存到集合中去
}
//对那些移动时不会超出数组的元素开始移动
for(int i = n - 1 - m ; i >= 0; i --){
a[i + m] = a[i];
}
//最后将集合中的元素直接从开头按顺序存放就可以
for(int i = 0 ; i < rest.size() ; i ++){
a[i] = rest.get(i);
}
return a;
}
}
发表于 2022-03-13 14:32:30
回复(0)
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) {
// write code here
for(int i = 0; i < m; i++){
youYi(a);
}
return a;
}
public void youYi(int[] a){
int tail = a[a.length - 1]; // 获取最后一个元素
// 循环右移
for(int i = a.length - 1; i >= 1; i--){
a[i] = a[i - 1];
}
a[0] = tail;
}
}
发表于 2021-12-22 13:01:17
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-19 10:00:35
-
2022-09-16 18:34:12
-
2022-09-16 15:48:27
-
2022-09-16 15:44:08 -
2022-09-16 15:18:43
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
