-
Notifications
You must be signed in to change notification settings - Fork 0
/
rotate.js
72 lines (70 loc) · 1.44 KB
/
rotate.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
/** O(nk)
let rotate = function (nums, k) {
for (let i = 0; i < k; i++) {
nums.unshift(nums.pop())
}
}
*/
/** O(nk)
let rotate = function (nums, k) {
let len = nums.length
let newK = k % len
let temp
for (let i = 0; i < newK; i++) {
temp = nums[len - 1]
for(let j = len - 2; j >= 0; j--) {
nums[j + 1] = nums[j]
}
nums[0] = temp
}
// return nums
}
console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3))
*/
/** On
let rotate = function (nums, k) {
function reverse(nums, left, right) {
for (; left < right; left++, right--) {
[nums[left], nums[right]] = [nums[right], nums[left]]
}
}
let len = nums.length
k %= len
reverse(nums, 0, len - k - 1)
reverse(nums, len - k, len - 1)
reverse(nums, 0, len - 1)
}
console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3))
*/
// http://blog.thpiano.com/?p=251
let gcd = function (m, n) {
let res
while (res = m % n) {
m = n
n = res
}
return n
}
let rotate = function (nums, k) {
let len = nums.length
k = len - (k % len)
for (let i = 0, cnt = gcd(len, k); i < cnt; i++) {
let temp = nums[i],
pos = i,
j = (k + i) % len
while (j != i) {
nums[pos] = nums[j]
pos = j
j = (k + pos) % len
}
nums[pos] = temp
console.log(nums)
}
return nums
}
console.log(rotate([1, 2, 3, 4, 5, 6], 4))