当前位置:   article > 正文

[LeetCode]189. 轮转数组(java实现)双指针算法_leetcode 轮转数组java

leetcode 轮转数组java

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

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

思路(双指针算法):

如有如下数组 1 2 3 4 5k = 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--;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

可能存在的问题:

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

  • 双指针算法翻转数组

6. 总结

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/767075
推荐阅读
相关标签
  

闽ICP备14008679号