LeetCode Rotate Array 翻转数组
2024-08-23 15:15:45
题意:给定一个数组,将该数组的后k位移动到前n-k位之前。(本题在编程珠玑中第二章有讲)
思路:
方法一:将后K位用vector容器装起来,再移动前n-k位到后面,再将容器内k位插到前面。
class Solution {
public:
void rotate(int nums[], int n, int k) {
if( !k || !n || n== || k==n ) return;
k %= n;
vector<int> cha;
cha.reserve(k);
int i;
for(i=n-k; i<n; i++)//装进容器
cha.push_back(nums[i]);
for(i=n-k-; i>=; i--)//移动前n-k位
nums[i+k]=nums[i];
for(i=; i<k; i++)//将容器内k个元素移到前面
nums[i]=cha[i];
}
};
Rotate Array
方法二:将后k位自身旋转,再将前n-k位自身旋转,在将整个数组旋转。例如:[1,2,3,4,5,6,7],第一步[1,2,3,4,7,65],第二步[4,3,2,1,7,6,5],第三步[5,6,7,1,2,3,4]。主要工作就是旋转,
class Solution {
public:
void rev(int *q,int *p) //将q与p所指向的区间旋转
{
while( q!=p && q!=p+ )
{
*q ^= *p;
*p ^= *q;
*q ^= *p;
q++;
p--;
}
} void rotate(int nums[], int n, int k) {
if( !k || !n || n== || k==n ) return;
k %= n;//这一步很必要
rev(&nums[n-k],&nums[n-]);//转后k个
rev(&nums[],&nums[n-k-]);//转前n-k个
rev(&nums[],&nums[n-]);//转整个
}
};
Rotate Array
方法三:为了省空间,当n%k==0时,就可以用这招了。将最后一位取出来,该位置-k的位置上的值就可以放在最后一位上了,其实就是按周期k,将各个元素一步到达其最终的位置上。例如[1,2,3,4,5,6,7,8,9],k=3,先将9用一个变量存起来,那么6就可以移到9的位置上,3就可以移到6的位置上,9可以移到3的位置上。对于8、5、2也是如此。这样就能完成节省空间的目的了。但是,当n%k不为0时,要注意了,按上面做法移动完之后,最前面的k位并不在其最终位置上,比如
[1,2,3,4,5,6,7],k=3,结果却是
[7,5,6,1,2,3,4],第一步是7、4、1没错吧?那7就到了1的位置了,第二步是6、3没错吧,那么只是交换了他们的位置。那么7在第1位,6在第3位,5在第2位,这可以想办法解决的。办法是,前k位中的前(n%k)个元素得接在后面k-(n%k)位的后面,又需要进行一次旋转,太麻烦了,如果这次k%(n%k)又不为0,那么还有得继续!我用的方法是对这前k位直接套用上面第2种方法。速度奇慢!
class Solution {
public:
void rev(int *q,int *p)
{
while( q!=p && q!=p+ )
{
*q ^= *p;
*p ^= *q;
*q ^= *p;
q++;
p--;
}
} void rotate(int nums[], int n, int k) {
if( !k || !n || n== || k==n ) return;
k %= n;
int temp, i, j;
for(i=; i<=k; i++)
{
temp = nums[n-i];
cout<<temp<<endl;
for(j=n-i-k; j>=; j-=k)
{
nums[j+k] = nums[j];
cout<<nums[j+k]<<endl;
}
nums[j+k] = temp;
}
temp=n%k;
//套用第2种方法
rev(&nums[],&nums[temp-]);
rev(&nums[temp],&nums[k-]);
rev(&nums[],&nums[k-]);
}
};
Rotate Array
最新文章
- leetcode36. Valid Sudoku
- Oracle主库归档丢失,备库日志有gap,在不重建备库的情况下,恢复备库
- EL表达式详解
- React Native教程 - 调用Web API
- Ubuntu配置ssh server
- xmlDoc.SelectNodes用法(获取不到节点时注意事项)
- POJ 1080 Human Gene Functions -- 动态规划(最长公共子序列)
- MongoDB源码分析——mongo主程序入口分析
- Android版多线程下载器核心代码分享
- React 笔记
- windows phone 8.1开发:文件选择器FileOpenPicker
- Linux redhat ICE环境安装
- Educational Codeforces Round 5
- npm 如何查看一个包的版本信息?
- Select逻辑顺序图
- 3. tomcat 内存设置
- JavaSE回顾及巩固的自学之路(四)——————方法和数组,面向对象
- 【nginx】大文件下载
- nutch爬取时Exception in thread “main” java.io.IOException: Job failed!
- linux环境下pdo加载问题