旋转数组

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

可以考虑三层循环

数组1,2,3,4,5,6 数组长度 6,反转2,

第一次反转:6,5,4,3,2,1
第二次反转:5,6,4,3,2,1
第三次反转:5,6,1,2,3,4

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
        //例如n = 6 ,m = 7 这种情况需要会出现数字越界,并且长度为n旋转没有变化,所以进行取余
        m = m%n;
        reverse(a,0,n-1);
        reverse(a,0,m-1);
        reverse(a,m,n-1);
        return a;
    }
    
    public void reverse(int[] num,int start,int end){
        while(start<end){
            int temp = num[end];
            num[end] = num[start];
            num[start] = temp;
            start++;
            end--;
        }
    }
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容