leetcode/rotate-array.js at develop · imcoddy/leetcode · GitHub

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**
 * Source:  https://leetcode.com/problems/rotate-array/
 * Tags:    [Array]
 * Level:   Easy
 * Updated: 2015-04-24
 * Title:   Rotate Array
 * Auther:  @imcoddy
 * Content: Rotate an array of n elements to the right by k steps.
 * For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
 *
 * Note:
 * Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
 *
 *
 * [show hint]
 * Hint:
 * Could you do it in-place with O(1) extra space?
 *
 *
 * Related problem: Reverse Words in a String II
 *
 * Credits:Special thanks to @Freezen for adding this problem and creating all test cases.
 */

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 * @time 264ms
 */
var rotate = function(nums, k) {
    k = k % nums.length;
    while (k) {
        var t = nums.pop();
        nums.unshift(t);
        k--;
    }
    //return nums;
};


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 * @time 180ms
 */
var rotate = function(nums, k) {
    k = k % nums.length;
    if (k > 0) {
        var first = nums.slice(0, nums.length - k);
        var last = nums.slice(nums.length - k);
        for (var i = 0; i < last.length; i++) {
            nums[i] = last[i];
        }
        for (var i = 0; i < first.length; i++) {
            nums[i + k] = first[i];
        }
    }
    //    console.log(nums);
    //    return nums;
};

/**
 * Memo: Slice the elements which need to be moved, and put it at front of the array.
 * Complex: O(n)
 * Runtime: 156ms
 * Tests: 33 test cases passed
 * Rank: A
 * Updated: 2015-06-14
 */
var rotate = function(nums, k) {
    if (nums.length > 1) {
        k = k % nums.length;

        var to_move = nums.slice(nums.length - k);
        for (var i = nums.length - k - 1; i >= 0; i--) {
            nums[i + k] = nums[i];
        }
        for (var i = 0; i < to_move.length; i++) {
            nums[i] = to_move[i];
        }
    }
};

/**
 * Memo: Rotate the array to right k times
 * Complex: O(n)
 * Runtime: 252ms
 * Tests: 33 test cases passed
 * Rank: C
 * Updated: 2015-11-10
 */
var rotate = function(nums, k) {
    if (nums.length <= 1) return;
    k = k % nums.length;
    for (var i = 0; i < k; i++) nums.unshift(nums.pop());
};


/**
 * Memo: Almost same as above, but move to left if k is large than half of length, to make less movement.
 * Complex: O(n)
 * Runtime: 183ms
 * Tests: 33 test cases passed
 * Rank: B
 * Updated: 2015-06-14
 */
var rotate = function(nums, k) {
    if (nums && nums.length) {
        k = k % nums.length;

        if (k > (nums.length >> 1)) {
            for (var i = 0; i < nums.length - k; i++) {
                nums.push(nums.shift());
            }
        } else {
            for (var i = 0; i < k; i++) {
                nums.unshift(nums.pop());
            }
        }
    }
    //console.log(nums);
};

console.log(rotate([1], 0));
console.log(rotate([1, 2], 1));
console.log(rotate([1, 2, 3, 4], 1));
console.log(rotate([1, 2, 3, 4], 2));
console.log(rotate([1, 2, 3, 4], 3));
console.log(rotate([1, 2, 3, 4], 4));
console.log(rotate([1, 2, 3, 4], 8));
console.log(rotate([1, 2, 3, 4], 9));
console.log(rotate([1, 2, 3, 4, 5, 6, 7, 8], 7));
console.log(rotate([1, 2, 3, 4, 5, 6, 7, 8], 23));
console.log(rotate([1, 2, 3, 4, 5, 6, 7, 8], 9));