方法一中使用额外数组的原因在于如果我们直接将每个数字放至它最后的位置,这样被放置位置的元素会被覆盖从而丢失。因此,从另一个角度,我们可以将被替换的元素保存在变量 \textit{temp}temp 中,从而避免了额外数组的开销。 我们从位置 00 开始,最初令 \textit{temp}=\textit{nums}[0]temp=nums[0]。根据规则,位置 00 的元素会放至 (0+k)\bmod n(0+k)modn 的位置,令 x=(0+k)\bmod nx=(0+k)modn,此时交换 \textit{temp}temp 和 \textit{nums}[x]nums[x],完成位置 xx 的更新。然后,我们考察位置 xx,并交换 \textit{temp}temp 和 \textit{nums}[(x+k)\bmod n]nums[(x+k)modn],从而完成下一个位置的更新。不断进行上述过程,直至回到初始位置 00。 容易发现,当回到初始位置 00 时,有些数字可能还没有遍历到,此时我们应该从下一个数字开始重复的过程,可是这个时候怎么才算遍历结束呢?我们不妨先考虑这样一个问题:从 00 开始不断遍历,最终回到起点 00 的过程中,我们遍历了多少个元素? 由于最终回到了起点,故该过程恰好走了整数数量的圈,不妨设为 aa 圈;再设该过程总共遍历了 bb 个元素。因此,我们有 an=bkan=bk,即 anan 一定为 n,kn,k 的公倍数。又因为我们在第一次回到起点时就结束,因此 aa 要尽可能小,故 anan 就是 n,kn,k 的最小公倍数 \text{lcm}(n,k)lcm(n,k),因此 bb 就为 \text{lcm}(n,k)/klcm(n,k)/k。 这说明单次遍历会访问到 \text{lcm}(n,k)/klcm(n,k)/k 个元素。为了访问到所有的元素,我们需要进行遍历的次数为 作者:LeetCode-Solution 链接:https://leetcode.cn/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间: 2023-02-17 17:46:44 浏览: 53
在方法一中使用额外数组的原因是:如果直接将每个数字放在它最终的位置,那么被放置的位置的元素会被覆盖,从而丢失。为了避免这种情况,我们使用额外数组来保存被替换的元素,这样就可以避免丢失元素。方法二中,使用变量 temp 保存被替换的元素,也可以避免丢失元素,但是这种方法不需要额外数组,因此可以节省空间开销。当第一次回到起点时,表示已经遍历了整数数量的圈,由于 aa 要尽可能小,所以 anan 就是 n,kn,k 的最小公倍数,这时就可以结束遍历了。
相关问题
如何将一个数组中的部分内容插入到空数组中
要将一个数组中的部分内容插入到一个空数组中,可以使用JavaScript的`Array.prototype.push()`方法或者数组展开运算符(spread operator)。
下面是两种方法的示例代码:
方法一:使用`Array.prototype.push()`方法
```javascript
// 原始数组
const array1 = [1, 2, 3, 4, 5];
// 部分内容插入到空数组中
const newArray1 = [];
newArray1.push(array1[0], array1[2], array1[4]);
console.log(newArray1); // 输出: [1, 3, 5]
```
方法二:使用数组展开运算符(spread operator)
```javascript
// 原始数组
const array2 = [1, 2, 3, 4, 5];
// 部分内容插入到空数组中
const newArray2 = [...array2.filter((_, index) => index % 2 === 0)];
console.log(newArray2); // 输出: [1, 3, 5]
```
在这两种方法中,我们首先定义了一个空数组`newArray`。然后,我们选择要插入的原始数组`array`的一部分内容。在方法一中,我们使用`Array.prototype.push()`方法将选定的元素添加到`newArray`中。在方法二中,我们使用数组展开运算符和`Array.prototype.filter()`方法来过滤出我们想要的元素,并将它们展开到`newArray`中。
无论你选择哪种方法,最终结果都是将原始数组中的部分内容插入到了空数组中。
对于一维数组int a[5]={16,17,18,19,20}; (1)用两种方法输出各元素的值。 (2)用两种方法输出各元素的地址值。 用c++编程
以下是使用C++语言输出数组元素值和地址值的两种方法:
方法一:
```cpp
#include <iostream>
using namespace std;
int main() {
int a[5] = {16, 17, 18, 19, 20};
// 输出各元素的值
for (int i = 0; i < 5; i++) {
cout << a[i] << " ";
}
cout << endl;
// 输出各元素的地址值
for (int i = 0; i < 5; i++) {
cout << &a[i] << " ";
}
cout << endl;
return 0;
}
```
方法二:
```cpp
#include <iostream>
using namespace std;
int main() {
int a[5] = {16, 17, 18, 19, 20};
// 输出各元素的值
for (int x : a) {
cout << x << " ";
}
cout << endl;
// 输出各元素的地址值
for (int &x : a) {
cout << &x << " ";
}
cout << endl;
return 0;
}
```
其中,方法一中使用下标访问数组元素,方法二中使用范围for循环访问数组元素。方法一中使用&符号获取数组元素的地址值,方法二中使用&符号获取循环变量x的地址值。