趣味算法题

越刷越上头的趣味算法题
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

三次反转法解决轮转数组问题

发布于 2024-03-14 | 更新于 2024-08-21

题目:189. 轮转数组[1]

如果您已经有思路了,或者是N刷了,可以先自己写一遍。

题目分析

这道题可以这样表述:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

例如:

1
2
输入: nums = [1,2,3,1,1,1,1], k = 3
输出: [1,1,1,1,1,2,3]

解题思路

观察以上案例,可以发现,通过三次反转法,可以达到我们需要的结果。为方便观察,我们假设数组是这样的:

nums = “=====>—>”; k = 3,假设k=3的位置刚好是第一个箭头结束的位置

result = “—>=====>”;

三次反转法:

  • 反转整个数组:<---<=====
  • 反转第一段:---><=====
  • 反转第二段:--->=====>;

这种方法的好处是只需要线性时间即可完成,时间复杂度为 O(n),且不需要使用额外的存储空间。

数组反转是一种常用的数组操作技巧,它不仅可以用于解决数组轮转问题,也常用于其他需要调整数组元素位置的场景。

这种方法的优点是它的空间复杂度为 O(1),即不需要额外的存储空间,同时它的时间复杂度为 O(n),因为每个元素只被移动有限次数。通过巧妙地利用数组反转,可以高效地解决数组轮转问题。

Java解法

下面是使用Java语言的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length; // 如果k大于数组长度,取模避免多余的旋转
reverse(nums, 0, nums.length - 1); // 反转整个数组
reverse(nums, 0, k - 1); // 反转前k个元素
reverse(nums, k, nums.length - 1); // 反转剩下的元素
}

// 辅助方法:用于反转数组从start到end的部分
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}

References


  1. 189. 轮转数组. Retrieved from https://leetcode.cn/problems/rotate-array/ ↩︎

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/algorithm/rotate-array.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。