[LeetCode]189. 轮转数组（java实现）双指针算法

[LeetCode]189. 轮转数组（java实现）双指针算法

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

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

思路（双指针算法）：

如有如下数组 1 2 3 4 5，k = 2, 可以用双指针算法来翻转数组，指针i指向第一个节点，指针j指向最后一个节点，交换指针i和指针j的值，然后i ++，j –；

① 先将整个数组进行翻转 ===》 5 4 3 2 1

② 再将左k个数进行翻转 ===》 4 5 3 2 1

③ 再将右n-k个数进行翻转 ===》 4 5 1 2 3

3. 解法

---------------------------------------------------解法---------------------------------------------------

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums,0,n-1); // 翻转整个数组
        reverse(nums,0,k - 1); // 翻转前k个数
        reverse(nums,k,n-1); // 翻转后n-k个数
    }
    // 将i和j直接的元素翻转
    public void reverse(int[] nums,int i,int j){
        while(i < j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

---

可能存在的问题：

4. 可能有帮助的前置习题 5. 所用到的数据结构与算法思想

• 双指针算法翻转数组

6. 总结

双指针算法是常用的翻转数组的原地算法。