-
Notifications
You must be signed in to change notification settings - Fork 0
/
189.轮转数组.ts
150 lines (145 loc) · 3.09 KB
/
189.轮转数组.ts
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/*
* @lc app=leetcode.cn id=189 lang=typescript
*
* [189] 轮转数组
*
* https://leetcode.cn/problems/rotate-array/description/
*
* algorithms
* Medium (44.13%)
* Likes: 1822
* Dislikes: 0
* Total Accepted: 640.9K
* Total Submissions: 1.5M
* Testcase Example: '[1,2,3,4,5,6,7]\n3'
*
* 给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
*
*
*
* 示例 1:
*
*
* 输入: nums = [1,2,3,4,5,6,7], k = 3
* 输出: [5,6,7,1,2,3,4]
* 解释:
* 向右轮转 1 步: [7,1,2,3,4,5,6]
* 向右轮转 2 步: [6,7,1,2,3,4,5]
* 向右轮转 3 步: [5,6,7,1,2,3,4]
*
*
* 示例 2:
*
*
* 输入:nums = [-1,-100,3,99], k = 2
* 输出:[3,99,-1,-100]
* 解释:
* 向右轮转 1 步: [99,-1,-100,3]
* 向右轮转 2 步: [3,99,-1,-100]
*
*
*
* 提示:
*
*
* 1 <= nums.length <= 10^5
* -2^31 <= nums[i] <= 2^31 - 1
* 0 <= k <= 10^5
*
*
*
*
* 进阶:
*
*
* 尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
* 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?
*
*
*/
// @lc code=start
/**
Do not return anything, modify nums in-place instead.
*/
function rotate(nums: number[], k: number): void {
const n = nums.length;
const m = k % n;
if (m <= 0) return;
let count = 0;
let start = 0;
while (count < nums.length) {
let current = start;
let temp = nums[(start + n - m) % n];
do {
[nums[current], temp] = [temp, nums[current]];
current = (current + m) % n;
count += 1;
} while (current !== start);
start += 1;
}
}
// @lc code=end
rotate([1, 2, 3, 4, 5, 6, 7], 3);
/**
* 逐个复制,想到的最直观的解法
* @param nums
* @param k
*/
function rotate1(nums: number[], k: number): void {
const n = nums.length;
const m = k % n;
if (m <= 0) return;
const tempList: number[] = [];
for (let i = 0; i < m; i++) {
tempList.push(nums[n - i - 1]);
}
for (let i = n - 1; i >= m; i--) {
nums[i] = nums[i - m];
}
for (let i = 0; i < m; i++) {
nums[i] = tempList[m - i - 1];
}
}
/**
* 做3次反转,非常有技巧性
* @param nums
* @param k
*/
function rotate2(nums: number[], k: number): void {
const n = nums.length;
const m = k % n;
if (m <= 0) return;
reverse(0, nums.length - 1);
reverse(0, m - 1);
reverse(m, n - 1);
function reverse(left: number, right: number) {
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left += 1;
right -= 1;
}
}
}
/**
* 环状替换,这里使用 count 来做计数,最小公约的计数用法容易忘
* @param nums
* @param k
* @returns
*/
function rotate3(nums: number[], k: number): void {
const n = nums.length;
const m = k % n;
if (m <= 0) return;
let count = 0;
let start = 0;
while (count < nums.length) {
let current = start;
let temp = nums[(start + n - m) % n];
do {
[nums[current], temp] = [temp, nums[current]];
current = (current + m) % n;
count += 1;
} while (current !== start);
start += 1;
}
}