平移数组(leetcode189)

将数组平移k位,可以使用暴力,但是有一种很巧妙的方法。O(n)时间复杂度,O(1)空间消耗。

远离是这样:

nums数组: “—–>–>”; k =3
结果要为 “–>—–>”;

我们可以做三次翻转。

reverse1: “—–>–>” 得到: “<–<—–”
reverse2: “<–” 得到: “–><—–”
reverse3: “<—–” 得到: “–>—–>”

 

public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

 

本文系作者 @ 原创发布在 噓だ。未经许可,禁止转载。

喜欢()
评论 (0)
热门搜索
37 文章
3 评论
11 喜欢
Top