牛客在线编程101-97 旋转数组

拼搏现实的明天。 2023-10-04 19:56 24阅读 0赞

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

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;
            } else {
        
                m = m % n;
                //一次翻转
                for(int i = 0; i < n/2; i++) {
        
                    int tmp = a[i];
                    a[i] = a[n - i - 1];
                    a[n - i - 1] = tmp;
                }
             
                //翻转前面m个
                for(int i = 0; i < m/2; i++) {
        
                    int tmp = a[i];
                    a[i] = a[m - i - 1];
                    a[m - i - 1] = tmp;
                }
    
                //翻转后面n-m个
                for(int i = 0; i < (n-m)/2; i++) {
        
                    int tmp = a[m + i];
                    a[m + i] = a[n - i - 1];
                    a[n - i - 1] = tmp;
                }
                return a;                      
            }
        }
    }