[Leetcode 189]轮转数组
2022/9/3 6:24:54
本文主要是介绍[Leetcode 189]轮转数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Leetocde189 轮转数组
这题能被用做mid题是因为一题多解,其中基于双指针的轮状数组解法是比较难的
1. 使用新数组
__直接把第i个元素移到第(i+k)%numsize位置,类似循环队列
void rotate(int* nums, int numsSize, int k) { int newArr[numsSize]; for (int i = 0; i < numsSize; ++i) { newArr[(i + k) % numsSize] = nums[i]; } for (int i = 0; i < numsSize; ++i) { nums[i] = newArr[i]; } }
2. 数组翻转+双指针
这种解法上次是在王道考研数据结构里面见过
一共进行三次翻转
class Solution { public: //编写翻转函数 void reverse(vector<int>& nums, int start, int end) { while (start < end) { swap(nums[start], nums[end]); start += 1; end -= 1; } } //分别进行三次翻转 void rotate(vector<int>& nums, int k) { k %= nums.size(); reverse(nums, 0, nums.size() - 1); reverse(nums, 0, k - 1); reverse(nums, k, nums.size() - 1); } };
3. 轮转数组
最优但是不好理解
这种解法是因为,只要确定了k值,实际上就可以直接确定某个元素移动之后下一个位置了,但是有些时候再次回到起点时,会陷入循环(此时还有未访问的元素),所以要从另一个新的起点出发循环
所以总的过程需要两个循环。内层循环还是比较简单的
主要难点是如何确定外层循环的次数?
两种解决方法
-
再定义一个变量,用来统计访问到的元素次数,只要访问完所有元素,整个过程就结束了
-
数学公式推导
YYSY,这个推导我想了很久才想明白。
关键是我们想要知道的是外层循环要多少次
如果我们知道一次小循环/内层循环(上图红色、蓝色分别为一个小循环)走过的元素个数,那么外层循环只需要总元素个数n/内层元素个数
就能计算出来了,不妨设内层小循环访问的元素个数为b
那么完成一次小循环走过的总步长为BK
又因为,从起点又回到终点,等价于一步一步走,走了n步,回到原点。那么一定存在一个整数a,使得an=bk。
如果还不好理解,就看这个例子
把环状数组想象成无限长的重复数列
-
[··· 1,2,3,4,1,2,3,4···]
k=2: 1->3->1,此时一个小循环只有两个元素,b=2,n=4 ==>a=1 -
[···1,2,3,4,5,1,2,3,4,5,1···]
k=2: 1->3->5->2->4->1 此时一个小循环中,b=5,n=5 ==>a=2
这篇关于[Leetcode 189]轮转数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升