对数组进行 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 次右旋转后的 Arr = [3 1 5 7 2 2 0]
第 4 个位置的元素 = 7
解决方法 1
我们将要讨论的解决方法将问题陈述视为两方面。这里有两个目标需要实现。它们如下：
将数组向右旋转 K 次。
返回修改后的数组的第 M 个元素。
任务 1：可以通过使用内置的 reverse() 函数来实现。以下试运行完美地演示了这一点。
让原始向量 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 |
现在反转整个 arr
| 4 | 5 | 1 | 2 | 3 |
因此，在执行 3 次反向操作后，我们将 arr 向右旋转 K 次。
任务 2：现在要找到第 M 个元素，我们只需返回 arr 中第 (M - 1) 个索引处的元素，因为我们遵循基于 0 的索引。
伪代码
function rightRotateByk(arr, k)
reverse(last K elements)
reverse(N - K initial elements)
reverse(all the elements)
end function
function solve(arr, k, m)
rightRotateByk(arr, k)
return arr[m - 1]
end function
function main()
Define arr[ ]
Initialise k
Initialise m
Declare ans
Function call solve(arr, k, m)
Store the result in ans
Output ans
end function
示例：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++ 程序用于确定第 M 个元素对原始数组进行 k 次右旋转后
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
// 函数将 arr 顺时针旋转 K 次
void rightRotateByk(vector<int> &arr, int k){
// 反转最后 K 个元素
reverse(arr.begin() + arr.size() - k, arr.end());
// 反转除最后 k 个元素之外的初始元素
reverse(arr.begin(), arr.begin() + arr.size() - k);
// 反转所有元素，向右旋转原始 arr K 次
reverse(arr.begin(), arr.end());
}
// 函数将 arr 进行 K 次右旋转后返回第 M 个元素
int resolve(vector<int> &arr, int k, int m){
rightRotateByk(arr, k);
// 返回第 M 个元素
return arr[m - 1];
}
int main(){
vector<int> arr = {5, 7, 2, 8, 0};
int k, m;
k = 2;
m = 2;
int ans = solved(arr, k, m);
cout << "K 次右旋转后第 M 个元素为： " << ans << endl;
return 0;
}
输出
K 次右旋转后第 M 个元素为：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)，则表示原始数组中的第 M 个元素位于向右旋转后剩余在开头的部分内。在本例中，我们计算原始数组中第 M 个元素的索引为 (M - K - 1)。
(M - K - 1) 表示数组开头剩余部分中元素的索引。
示例：C++ 程序
代码在执行 K 次右旋转后确定数组的第 M 个元素。它使用模数运算符处理 K 超出数组大小的情况。第 M 个元素的索引是根据 K 和 M 之间的关系计算的。最后，它返回旋转后原始数组中该索引处的元素。
示例
// C++ 程序在对原始数组进行 k 次右旋转后确定第 M 个元素
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 如果原始数组经过 K 次右旋转，则函数返回第 M 个元素
int solve(vector<int> arr, int K, int M){
int N = arr.size();
// (K % N) 将产生一个范围在 0 到 N-1 之间的值
K %= N;
int ind;
if (K >= M) {
// 这意味着原始数组中的第 M 个元素位于右旋转 K 部分内
ind = (N - K) + (M - 1);
}
else{
// 这意味着原始数组中的第 M 个元素位于右旋转后剩余在开头的部分内。
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 = solved(arr, k, m);
cout << "K 次右旋转后，第 M 个元素为：" << ans << endl;
return 0;
}
输出
K 次右旋转后，第 M 个元素为：7
时间和空间复杂度分析
程序以常数时间运行，不需要辅助空间。因此程序的时间和空间复杂度为O(1)。
结论
本文讨论了当数组向右旋转K次时返回数组第M个元素的两种方法。它提供了C++程序代码、伪代码以及时间和空间复杂度分析。
