极客笔记C++ 在数组右旋K次后找到第M个元素
将数组向右移动一定的位置称为右旋。在单个右旋中，数组的最后一个元素变为第一个元素，其余元素向右移动。
问题描述
目标是在执行K次右旋后找到数组的第M个元素，其中K和M是非负整数，数组包含N个元素。
示例示例
输入
arr = [12 34 56 21], K = 2, M = 1
输出
56
解释
K次右旋转后的Arr = [56 21 12 34]
第1个位置上的元素 = 56
输入
arr = [0 3 1 5 7 2 2], K = 6, M = 4
输出
7
解释
循环右移 K 次后的数组 = [3 1 5 7 2 2 0]
第四个位置的元素 = 7
解决方案方法 1
我们将讨论的解决方案方法将问题陈述为两个目标。这里有两个要实现的目标。它们如下：
- 将数组循环右移 K 次。
-
返回修改后数组的第 M 个元素。
任务 1：可以通过使用内置的 reverse() 函数来实现。下面的演示 perfectly 说明了这一点。
假设原始向量 arr 为 {1, 2, 3, 4, 5}
假设循环右移的次数(K)为 2
原始 arr
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
将数组 arr 的最后 K 个元素翻转
| 1 | 2 | 3 | 5 | 4 |
|---|---|---|---|---|
将arr数组的前 N – K 个元素反转
| 3 | 2 | 1 | 5 | 4 |
|---|---|---|---|---|
现在反转整个数组
| 4 | 5 | 1 | 2 | 3 |
|---|---|---|---|---|
经过3次反向操作后，我们将arr向右旋转K次。
任务2：现在要找到第M个元素，我们只需返回arr中第(M-1)个索引处的元素，因为我们采用以0为基准的索引。
伪代码
函数rightRotateByk(arr, k)
- 反向操作（最后K个元素）
-
反向操作（前N-K个初始元素）
-
反向操作（所有元素）
结束函数
函数solve(arr, k, m)
- rightRotateByk(arr, k)
-
返回arr[m – 1]
结束函数
函数main()
- 定义arr[]
-
初始化k
-
初始化m
-
声明ans
-
调用函数solve(arr, k, m)
-
将结果存储在ans中
-
输出ans
结束函数
示例：C++程序
代码确定原始数组经过K次右旋后第M个位置的元素。rightRotateByk（）函数用于以顺时针的方式将数组arr旋转K次。在rightRotateByk函数内部，执行了三次反向操作：
- 使用范围(arr.begin() + arr.size() – k, arr.end())反向arr的最后K个元素。
-
使用范围(arr.begin(), arr.begin() + arr.size() – k)反向arr的初始元素（不包括最后K个元素）。
-
反向arr的所有元素以完成右旋。
通过访问arr[m – 1]来返回旋转后数组的第M个元素，因为数组的索引从0开始。
示例
// C++ program to determine the element at the Mth number after subjecting the original array to k right rotations
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
// Function to rotate arr K times in clockwise manner
void rightRotateByk(vector<int> &arr, int k){
// reverse the last K elements
reverse(arr.begin() + arr.size() - k, arr.end());
// reverse the initial elements other than the last k elements
reverse(arr.begin(), arr.begin() + arr.size() - k);
// reverse all the elements to right rotate the original arr K times
reverse(arr.begin(), arr.end());
}
// Function to return the Mth element of arr after subjecting arr to K right rotations
int solve(vector<int> &arr, int k, int m){
rightRotateByk(arr, k);
// Return the Mth element of arr
return arr[m - 1];
}
int main(){
vector<int> arr = {5, 7, 2, 8, 0};
int k, m;
k = 2;
m = 2;
int ans = solve(arr, k, m);
cout << "Mth element after K right rotations is: " << ans << endl;
return 0;
}
输出
Mth element after K right rotations is: 0
时间和空间复杂度分析
时间复杂度：O(n)
- rightRotateByk函数执行三次反转操作，每个操作的时间复杂度都是线性的。因此，rightRotateByk的时间复杂度为O(n)，其中n是数组的大小。
-
此外，访问数组的第M个元素的时间复杂度是常数。
空间复杂度：O(1)
代码除了使用向量来存储输入数组之外，不使用任何辅助空间。
解决方案2
一个简单的洞察可以极大地优化代码。关键观察是，经过N次旋转后，原始数组将恢复，因为元素将回到其原始位置。基于此观察，我们可以利用取模运算符%来确定有效旋转次数。
- 对于任何正整数K，K%N将得到在0到N-1范围内的值。
-
如果K大于或等于M（K>=M），则意味着原始数组中的第M个元素在K次右旋转的部分内。在这种情况下，我们计算原始数组中第M个元素的索引为（N-K）+（M-1）。
- (N-K)表示被K次旋转向右移动的元素数量。
-
(M-1)表示在旋转部分中的索引偏移。
-
如果K小于M（K
- (M-K-1)表示数组开头剩余部分中元素的索引。
示例：C++程序
该代码确定在执行K次右旋转后数组的第M个元素。它通过使用取模运算符处理K超过数组大小的情况。根据K和M之间的关系，计算第M个元素的索引。最后，返回旋转后原始数组中该索引处的元素。
示例
// C++ program to determine the element at the Mth number after subjecting the original array to k right rotations
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to return the Mth element if the original array is subjected to K right rotations
int solve(vector<int> arr, int K, int M){
int N = arr.size();
// (K % N) will yield a value in the range of 0 to N-1
K %= N;
int ind;
if (K >= M) {
// This implies that the Mth element in the original array is within the K right-rotated portion
ind = (N - K) + (M - 1);
}
else{
// This means that the Mth element in the original array is within the portion that remains at the beginning after the right rotations.
ind = (M - K - 1);
}
return arr[ind];
}
int main(){
vector<int> arr = {0, 3, 1, 5, 7, 2, 2};
int k, m;
k = 6;
m = 4;
int ans = solve(arr, k, m);
cout << "Mth element after K right rotations is: " << ans << endl;
return 0;
}
输出结果
Mth element after K right rotations is: 7
时间和空间复杂度分析
程序在恒定时间内运行，并且不需要额外的空间。因此，该程序的时间和空间复杂度为O(1)。
结论
本文讨论了两种方法，用于返回数组在向右旋转K次的情况下的第M个元素。它提供了C++程序代码、伪代码以及时间和空间复杂度分析。