日常算法—数组整体向右移动K位(三次倒置C++实现)

浅浅的花香味﹌ 2022-11-05 05:25 149阅读 0赞

#### 题目重述 ####

给定n,k和一个数组，n是数组的大小，k是向移动的位次

例如输入5和2，代表将数组的前五位向右移动K位

5 2
    1 2 3 4 5

输出

4 5 1 2 3

#### 思路 ####

有一个比较巧的方法就是，使用三次倒置实现，例如初始数据是1 2 3 4 5

第一次是**全倒置**

5 4 3 2 1

第二次是前K位倒置

4 5 3 2 1

第三次是后n-k个位倒置，即

4 5 1 2 3

#### C++ 代码实现 ####

输出数组函数，便于直观观察

void print(int arr[20],int n)
    {
        
    	for(int i=0;i<n;i++)
    	{
        
    		cout<<arr[i]<<" ";
    	}
    	cout<<endl;
    }

具体实现

int main(int argc, char** argv) {
        
    	int arr[20],n,k;
    	// 输入 
    	cin>>n>>k;
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>arr[i];
    	}
    	// 全倒置 
    	for(int i=0;i<(n/2);i++)
    	{
        
    		swap(arr[i],arr[n-i-1]);
    	}
    	print(arr,n);
    	// 前半部分倒置 
    	for(int i=0;i<(k/2);i++)
    	{
        
    		swap(arr[i],arr[k-i-1]);
    	}
    	print(arr,n);
    	// 后半部分倒置 
    	for(int i=k;i<=(n+k)/2;i++)
    	{
        
    		swap(arr[i],arr[n+k-i-1]);
    	}
    	print(arr,n);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210304112653881.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20221023/6c741bb9675d438bb4f98c8da2231dc2.png
[20210304112653881.png]: /images/20221023/fe5f74138d964bef89019a39aebcdc10.png