当前位置：首页 > news >正文

马上深挖！！！三段逆置如何实现数组轮转？！用最简单的话让你秒懂

news 2026/5/26 0:56:23

一、目的

给定一个数组和一个整数k，让数组向右轮转k个数。如令[1,2,3,4,5,6]向右轮转3个数，结果为[4,5,6,1,2,3]。

二、代码

#include <iostream> using namespace std; void swap(int* a,int* b) { int tmp=*a; *a=*b; *b=tmp; return; } void reverse(int* a,int begin,int end) { int left=begin,right=end; while(left<right) { swap(a+left,a+right); left++; right--; } return; } void Rotate(int* a,int size,int k) { k%=size; //数组整体逆置 reverse(a,0,size-1); //对*B逆置 reverse(a,0,k); //对*A逆置 reverse(a,k,size-1); return; } void show(int* arr,int len) { for(int i=0;i<len;i++) cout<<arr[i]<<" "; return; } int arr[]={1,2,3,4,5,6,7}; int n=sizeof(arr)/sizeof(arr[0]); int main() { show(arr,sizeof(arr)/sizeof(arr[0])); Rotate(arr,n,4); cout<<endl; show(arr,n); return 0; }

三、解析

首先，我们把数组arr分成两段：第一段为A，长度k，剩下的部分作为第二段B。现在，如果A和B内部都只有一个数字，那么要实现arr逆序，只需arr整体逆序（即，让AB变成BA）。

理解了A、B都是单个元素的情况之后，我们就可以推广到A、B包含多个元素的情况。

当A、B包含多个元素时：延续之前的思路，我们对arr整体逆置（注意！当A、B包含多个元素，对arr整体逆置不仅会对调 A、B的位置，还会让A、B内部分别发生逆置。我们设A逆置的结果为A*，B逆置的结果为B*），则数组从AB变成了B*A*，此时，为了实现我们的目标（即BA），只需再对*B和*A分别进行一次逆置，就可让*B*A变成BA，完成！

四、细节

数组的轮转就一个转盘：若向右轮转的位数k等于arr的长度size，则会轮转一圈，回到原来的样子。所以，考虑到这个问题的“周期性”，我们需要对k进行处理：若k>=size，则会造成数组的越界，无法实现正常的轮转。所以，根据处理“周期性问题”的通法，对k取模（k%=size），让k处于范围0~size-1内，便能在k过大时实现正常的轮转。