LeetCode 189.轮转数组

2023-04-26

int nums tmp

文章目录💡题目分析💡解题思路🚩思路1:暴力求解---旋转k次🔔接口源码：🚩思路2:额外开数组🔔接口源码：🚩思路3:三段逆置📍算法设计🔔接口源码：题目链接👉LeetCode189.轮转数组👈💡题目分析给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。💡

文章目录

💡题目分析
💡解题思路
- 🚩思路1:暴力求解 --- 旋转k次
- 🔔接口源码：
- 🚩思路2:额外开数组
- 🔔接口源码：
- 🚩思路3:三段逆置
- 📍算法设计
- 🔔接口源码：

题目链接👉LeetCode 189.轮转数组👈

💡题目分析

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

💡解题思路

🚩思路1:暴力求解 — 旋转k次

假如我们要把数组 [1,2,3,4,5,6,7]，向右旋转3次

👇图解👇

第1步：定义一个临时变量 tmp，用来存放数组最后的元素7
第2步：把数组前 n-1 个值往后挪
第3步：把 tmp 的值放入前面空位置中去

👆这样就完成了 1 次轮转，如果要轮转 k 次，就需要循环 k 次就完成了

🔔接口源码：

void rotate(int* nums, int numsSize, int k)
{
    k %= numsSize;//防止k大于numsSize
    int tmp = 0;
    for (int i = 0; i < k; i++)
    {
        tmp = nums[numsSize - 1];
        for (int j = numsSize - 1; j > 0; j--)
        {
            nums[j] = nums[j - 1];
        }
        nums[0] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

此方法：
时间复杂度：O(N^2) — 最坏情况
空间复杂度：O(1)

🚨但是这种解法是过不了的，LeetCode会限制效率，这种方法效率太低了

🚩思路2:额外开数组

以 空间换时间 的做法

👇图解👇

第1步：新开辟一个数组
第2步：把后 k 个元素放到新数组的前面
第3步：再把前 n-k 个元素放到新数组的后面（n是数组中元素总个数也就是题目中的参数 numsSize）

🔔接口源码：

void rotate(int* nums, int numsSize, int k)
{
if (k > numsSize)
{
k %= numsSize;
}
int* tmp = (int*)malloc(sizeof(int) * numsSize);

memcpy(tmp, nums + numsSize - k, sizeof(int) * k);
memcpy(tmp + k, nums, sizeof(int) * (numsSize - k));
memcpy(nums, tmp, sizeof(int) * (numsSize));
free(tmp);
tmp = NULL;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

此方法：
时间复杂度：O(N)
空间复杂度：O(N)

🚩思路3:三段逆置

🥰非常绝绝子的方法！！！

👇图解👇

第1步：对前 n-k 个逆置
第2步：对后 k 个逆置
第3步：整体逆置

此方法：
时间复杂度：O(N)
空间复杂度：O(1)

📍算法设计

先写一个逆置的函数来实现逆置的功能👇

void reverse(int* arr, int left, int right)
{
while (left < right)
{
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
}
}
1
2
3
4
5
6
7
8
9
10
11

🚨我们使用 reverse逆置函数的时候要注意：数组下标是从 0 开始的
🚨我们还需要注意一个问题：如果 k 超过了数组元素个数怎么办？

比如：数组是 [ 1 2 3 4 5 6 7] ，k = 8 的时候，此时数组元素个数为 7，而要求向右旋转 8 个位置，如果按照上面分析的情况，第一趟对前 n - k 逆置，也就是 7-8个逆置，难道对前 -1 个逆置吗？

仔细想一下最后的结果会是什么？
结果数组就是 [ 7 1 2 3 4 5 6 ]
🚨我们要记住这道题的核心叫 轮转数组，也就是当轮转的次数超过数组长度的时候，又是新的一轮了！

所以，如果 k 大于数组长度，故首先对 k 取余，然后再次旋转，这不会影响最终结果！

🔔接口源码：

void reverse(int* arr, int left, int right)
{
while (left < right)
{
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
}
}

void rotate(int* nums, int numsSize, int k) 
{
    if(k>numsSize)
    {
        k%=numsSize;
    }
   reverse(nums, 0, numsSize-k-1);
   reverse(nums, numsSize-k, numsSize-1);
   reverse(nums, 0, numsSize-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22