🌕 🌗 189. 轮转数组

难度: 🌕 🌗

问题描述

---

解法 1 - 常规思路

class Solution {
    public void rotate(int[] nums, int k) {
        // 思路：
        // new[0] = old[len - k % len]
        // new[?] = old(len - k % len + ?) % len
        // 构造新数组，把原值复制过来
        int len = nums.length;
        int[] res = new int[len];
        int step = len - k % len;
        for(int i = 0; i < len; i ++) {
            res[i] = nums[(i + step) % len]; 
        }
        System.arraycopy(res, 0, nums, 0, len);
    }
}

---

输出 1

---

解法 2 - O(1) 原地交换

class Solution {
    public void rotate(int[] nums, int k) {
        // 思路：
        // new[0] = old[len - k % len]
        // new[?] = old(len - k % len + ?) % len
        // 保存原下标的值，进行原地交换
        // 需要注意的是，不一定一遍就能交换完所有元素，存在一遍的环没有完全覆盖的情况
        int len = nums.length;
        int[] res = new int[len];
        int step = len - k % len;
        int count = 0;
        for(int i = 0; i < len; i ++) {
            // i 为当前覆盖环的起始下标
            int store = nums[i];
            int origIndex = i; // 防止转圈
            int cur = i; // cur 下标值应该被替换
            int next = (cur + step) % len; // cur 被替换为 next 处的值
            while(next != origIndex) {
                nums[cur] = nums[next];
                count ++;
                cur = next;
                next = (cur + step) % len;
            }
            // next == origIndex
            nums[cur] = store;
            count ++;
            if(count >= len) {
                return;
            }
        }
    }
}

---

输出 2

---

解法 3 - 翻转再翻转

class Solution {
    public void rotate(int[] nums, int k) {
        // 思路：
        // method 3 - 
        // 这种情况没做过是真的想不出来
        // [0 1 2 3 4 5] k = 4, len = 6
        // [5 4 3 2 1 0] 完全翻转
        // [2 3 4 5 0 1] [0, 3] 完全翻转，[4, 5]完全翻转 得到结果
        int len = nums.length;
        mySol(nums, 0, len - 1);
        int step = k % len;
        mySol(nums, 0, step - 1);
        mySol(nums, step, len - 1);
    }

    private void mySol(int[] nums, int left, int right) {
        while(left < right) {
            swap(nums, left, right);
            left ++;
            right --;
        }
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

---

输出 3