数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学查找数组经 K 次右旋转后的第 M 个元素
数组右旋转是指将数组的元素向右移动一定数量的位置。在一次右旋转中，数组的最后一个元素成为第一个元素，其余元素向右移动。
问题陈述
目标是在执行 K 次右旋转后查找数组的第 M 个元素，其中 K 和 M 是非负整数，数组包含 N 个元素。
示例
输入
arr = [12 34 56 21], K = 2, M = 1
输出
56
解释
K 次右旋转后的数组 = [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]
第 4 个位置的元素 = 7
方法一
我们将要讨论的解决方案将问题陈述视为两个方面。这里有两个目标需要完成。它们如下所示：
将数组右旋转 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 的索引。
伪代码
函数 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)
代码除了用于存储输入数组的向量外，没有使用任何辅助空间。
方法二
一个简单的见解可以极大地优化代码。关键观察是，经过 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 超过数组大小的情况。根据 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)。
结论
本文讨论了两种方法来返回数组的第 M 个元素，如果将其右旋转 K 次。它提供了 C++ 程序代码、伪代码以及时间和空间复杂度分析。
73 次浏览
