张伦聪的技术博客 Research And Development

189. 旋转数组

2018-04-21

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

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

提示:

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

关联的问题: 反转字符串中的单词 II

解:要注意k有可能大于数组长度,所以需要取余来得到真正需要旋转的步数,不然ac不了

  举一个例子: 

  1 2 3 4 5 6 7  如果k = 3 的话, 会变成 5 6 7 1 2 3 4

  1 2 3 4 5 6 7  middle = 7 - 3 = 4,分为左边 4个数字,右边 3个数字

  4 3 2 1 7 6 5  分别把左右reverse 一下

  5 6 7 1 2 3 4  把总数组reverse 一下就会得到答案
    public void rotate(int[] nums, int k) {
        int turns = k % nums.length;
        int mid = nums.length - 1 - turns;
        reverse(nums, 0, mid);
        reverse(nums, mid + 1, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
    }

    private void reverse(int[] nums, int s, int e) {
        while (s < e) {
            int tmp = nums[s];
            nums[s] = nums[e];
            nums[e] = tmp;
            s++;
            e--;
        }
    }

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

¥ 打赏博主

类似文章

上一篇 283. 移动零

留言