当前位置：首页 > article >正文

【题解-力扣189. 轮转数组（java实现O(1)空间要求）】

article 2024/11/15 22:59:16

一、题目描述

题目链接：https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

二、解题思路

如果只考虑简单的方法，不考虑O(1)空间，那必然是新建一个n长度的数组res，将n-k~n的数据依次插入数组res，随后将0-n-k-1的数据插入，就完事了
考虑O(1)空间，则要清楚所有的交换动作需要在数组本身上面完成。
1、模拟一下，k>n/2和k<n/2的两种情况
2、实际上每一次操作都是将原来数组切割成两个子数组，然后用两个子数组中长的数组剩余的数据和两个交换成功的部分的后边数据组成的子数组继续进行交换操作。
3、例如：1,2,3,4,5,6,7 k=3。第一步：分割成(1,2,3,4)和(5,6.7)进行交换。第二步，数组变为（5，6，7，4，1，2，3），4作为剩余数组组成子数组（4），和（1，2，3）进行交换。第三步，数组变为（5，6，7，1，4，2，3），剩余数组组成（2，3）和（4）进行交换。第四步，数组变为（5，6，7，1，2，4，3），（3）和（4）交换，变为（5，6，7，1，2，3，4）达到理想效果。第二个案例可以用类似模拟方法得到规律。下面直接上代码。

三、代码

class Solution {
    public void rotate(int[] nums, int k) {

        k = k %  nums.length ;
        if(k == 0 ){
            return;
        }
        //思路：将数组切割成两份
        //子数组互相交换 如果有一个剩下元素的子数组
            //该剩下的子数组和之前交换成功的两个子数组其中后置数组继续交换
        f(nums,0, nums.length-k-1, nums.length-k, nums.length-1);
        
    }
    public void f(int[] nums,int op1 , int ed1 , int op2,int ed2){
    while(op1 <= ed1 && op2 <= ed2){
            int temp = nums[op1];
            nums[op1] = nums[op2];
            nums[op2] = temp;
            op1++;
            op2++;
        }
        if(op1 > ed1 && op2 > ed2){
            return;
        }
        if(op1 == ed1 + 1){
            f(nums,op1,op2-1,op2,ed2);
        }
        if(op2 == ed2 + 1) {
            f(nums,op1,ed1,ed1+1,ed2);
        }

    }
}