平移数组(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--; } }
本文系作者 @rinbn 原创发布在 噓だ。未经许可,禁止转载。