旋转数组（java实现）

一、题目

新年第一题，避免老年痴呆！
题源：牛客

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

数据范围：整数范围
进阶：空间复杂度O(1) ，时间复杂度O(n)

例：
6,2 [1,2,3,4,5,6]
[5,6,1,2,3,4]

二、思路

1. 将数组 0 ~ n-m-1 的子数组翻转一下。（4,3,2,1,5,6）
2. 将数组n-m ~ n-1 的子数组翻转一下。（4,3,2,1,6,5）
3. 将数组0 ~ n-1 直接翻转一下。（5,6,1,2,3,4）
4. over !

三、代码

 public static void main(String[] args) {
        //一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，
        // 即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）
        // （最后 M 个数循环移至最前面的 M 个位置）。
        // 如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
        //
        //数据范围：，
        //进阶：空间复杂度 ，时间复杂度

        // 6,2 [1,2,3,4,5,6]
        // [5,6,1,2,3,4]

        // 1、现将1~n-m数据翻转 n-m~n数据翻转 最后将1~n数据翻转
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        ArrayList<Integer> nums = new ArrayList<>();
        for(int i = 0 ; i < n ; i++){
            int num = scanner.nextInt();
            nums.add(num);
        }
        overturn(nums,0,n-m-1);
        overturn(nums,n-m,n-1);
        overturn(nums,0,n-1);
        System.out.println(nums);
    }

    public static void overturn(List<Integer> nums , int start,int end){
        int mid = (start + end)/2;
        for(int i=start; i<=mid; i++){
            //交换
            Integer startNum = nums.get(i);
            nums.set(i,nums.get(end));
            nums.set(end,startNum);
            end--;
        }
    }

ps:仅提供思路，不保证代码能oc

原文地址：https://blog.csdn.net/qq_44816011/article/details/136151381

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！