leetcode 189.旋转数组
2021-04-01 09:25
标签：png swa private 自己实现 赋值 span 问题 数组 四种 官方解题给出了四种解法。 第一种，暴力法，时间复杂度O（n*k）。 第二种，额外构建一个等大数组，将额外数组作为中介进行两次全数组的拷贝。时间代价为O（n）。空间代价也为O（n）。 第三种，环状替换，也是我自己实现的方法。时间代价O（n）,空间代价O（1）。 如果我们直接把每一个数字放到它最后的位置，但这样的后果是遗失原来的元素。因此，我们需要把被替换的数字保存在变量temp 里面。然后，我们将被替换数字（temp）放到它正确的位置，并继续这个过程 n次， n是数组的长度。这是因为我们需要将数组里所有的元素都移动。但是，这种方法可能会有个问题，如果n%k==0，其中 k=k%n （因为如果 k 大于 n ，移动 k 次实际上相当于移动 k%n 次）。这种情况下，我们会发现在没有遍历所有数字的情况下回到出发数字。此时，我们应该从下一个数字开始再重复相同的过程。 实际上，形成的环数（我自己更愿意称为切片数）=数组长度n和移动距离k的最大公约数。从这一点出发，对每个环进行循环替换。 代码如下 以上的数据位移我是用swap实现的，可能并不符合直观的感受，但是实际是可行的，如果按正常的思路循环替换，那么需要两个额外变量。这里我只用了一个额外变量。而且在时间上的代价应该是差不多的。。除非频繁的swap函数调用占了很多时间，具体没有试过。 最大公因数这个for循环的边界条件确实比较难想到，一个小技巧是可以用移动过的元素数count作为循环边界条件，那么就不需要计算最大公因数了。 第四种方法是使用反转。这就很巧妙了。 leetcode 189.旋转数组 标签：png swa private 自己实现 赋值 span 问题 数组 四种 原文地址：https://www.cnblogs.com/dongjl/p/13532751.html 1 class Solution {
2 public:
3 void rotate(vectorint> &nums, int k) {
4 int len = nums.size();
5 k = k % len;
6 if (k == 0)return;
7 int l= gongyin(len, k);
8 int p = len / l;//l个切片，每个切片p个元素
9 for (int i = 0; i i) {
10 for (int j = 0; j 1; ++j) {
11 swap(nums[i], nums[(i + (j + 1) * k) % len]);
12 }
13 }
14
15 }
16
17 private:
18 void swap(int &a, int &b) {
19 int temp;
20 temp = a;
21 a = b;
22 b = temp;
23 }
24
25 int gongyin(int &a, int &b) {
26 int num1 = 0, num2 = 0, c = 0; //num1,num2作为计算时的变量，c作为中间变量
27 if (a >= b) {
28 num1 = a;
29 num2 = b;
30 } else {
31 num1 = b;
32 num2 = a;
33 } //通过比较对num1和num2赋值，便于计算
34 while (num2 > 0) {
35 c = num1 % num2;
36 num1 = num2;
37 num2 = c;
38 } //辗转相除，num2=0时，num1=最大公因数
39 return num1;
40 }
41
42 };
