LeetCode（初级算法）数组篇---旋转数组

绝地灬酷狼 2022-05-26 07:10 193阅读 0赞

## 题目 ##

将包含 *n* 个元素的数组向右旋转 *k* 步。

例如，如果 *n* = 7 , *k* = 3，给定数组 `[1,2,3,4,5,6,7]` ，向右旋转后的结果为 `[5,6,7,1,2,3,4]`。

**注意:**

尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。

\[[显示提示\]][Link 1]

**提示:**

要求空间复杂度为 O(1)

## 解析 ##

*  做这道题之前需要知道，k是以一个数组长度为循环周期。
    
    所以无论是什么方法，都应该在开始时就完成`k=k%nums.length;`

### 方法一 ###

*  第一种方法是最为直接的，按照逻辑上对旋转怎么理解，就让程序怎么执行
 *  需要一个临时变量
 *  这种方法简单易懂，但==效率很低==

**Example:每旋转1次的执行过程**

1）先将最后一个保存到临时变量
    1   2   3   4   5   6   7   8    [8]---临时变量
    2）位移
    _   1   2   3   4   5   6   7   [8]---临时变量
    3) 将临时变量放到第一个
    8   1   2   3   4   5   6   7

**代码**

public class Solution { 
        @Test
        public void rotate(int[] nums, int k) {
            k = k % nums.length;
    
            for (int count = 0; count < nums.length; count++) {   //执行趟数
                int temp = nums[nums.length - 1];
                for (int j = nums.length - 1; j > 0; j--) {
                    nums[j] = nums[j - 1];
                }
                nums[0] = temp;
            }
        }
    }

### 方法二 ###

*  第二种方法用得是正则表达式，通过StringBuffer将旋转后的结果添加入缓冲区，再用Matcher进行筛选
 *  这种方法比较适用于==数组长度较大的旋转==，时间复杂度较高，但空间复杂度较低
    
        public class Solution3 { 
        private static String REGEX = "[+-]?\\d+";
        
        public void rotate(int[] nums, int k) {
            k=k%nums.length;
        
            StringBuffer str = new StringBuffer();
            int index = nums.length-k; 
              //time在这里作为趟数，也作为偏移量
            for(int time=0;time<nums.length;time++) {  
                str.append(nums[(index + time) %nums.length]);
                str.append(' '); 
            }
               //编译正则表达式
            Pattern p =Pattern.compile(REGEX); 
              //进行匹配
            Matcher m =p.matcher(str);
            int i=0;
            while(m.find()) {
                nums[i++]= Integer.valueOf(str.substring(m.start(),m.end()));
            }       
        }
        }

### 方法三 ###

*  第三种方法，是通过调用System.arraycopy和使用Arrays.copyOfRange完成，对数组内容的复制和移动
 *  这种方法执行==速度很快（System.arraycopy 是 本地方法）==，但是空间复杂度会比较高

**代码**

public void rotate(int[] nums, int k) {
            k=k%nums.length;
            // 返回 下标 为 nums.length-k到最后一个元素的子数组temp
            int temp[] = Arrays.copyOfRange(nums,nums.length-k ,nums.length); 
             // 将剩余的元素复制到旋转后的位置
            System.arraycopy(nums, 0, nums, k, nums.length-k);
             // 将temp复制到nums的开头
            System.arraycopy(temp, 0,nums , 0, k);
        }

**图解**

1) 初始状态
    nums:   1   2   3   4   5   6   7   8
    k:  3
    2) 取出子集
    nums:   1   2   3   4   5   6   7   8
    temp:   6   7   8
    3) 将剩余的元素复制到旋转后的位置
    nums:   1   2   3   1   2   3   4   5
    temp:   6   7   8
    4) 将temp复制到nums的开头
    nums:   6   7   8   1   2   3   4   5

## 拓展 ##

**数组的复制**

*  System.arrayscopy（源数组，起始位置，目标数组，起始位置，复制长度）—-本地方法

\*可以复制到自己身上

Eg：System.arrayscopy（obj，0，obj，3，3）：表示数组里的前三个字符向右移动3个位置

*  Arrays.copyOf(目标数组，新的长度)—– 返回新数组
    
    
 *  Arrays.copyOfRang(目标数组，起始位置，结束位置)—–返回新数组

**与System.arrayscopy不同的是：==复制区间是从起始位置，到结束位置的前一个元素==**

[Link 1]: https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/23/#