C++ 程序在数组右旋转 K 次后查找第 M 个元素
右旋转意味着我们必须将每个元素向右移动，因为第 0 个索引元素移到第 1 个索引，第 1 个索引元素移到第 2 个索引，...，最后一个元素移到第 0 个索引。这里我们给出了一个大小为 n、整数 m 和整数 k 的整数数组。我们的任务是在数组右旋转 k 次后找到第 m 个元素。
以下是一些示例和说明，可帮助您理解该问题。
示例
输入
数组:[ 1, 3, 2, 5, 6, 7 ], k: 2, m: 4
输出
3
说明:第一次右旋转:[ 7, 1, 3, 2, 5, 6 ]
第二次右旋转:[ 6, 7, 1, 3, 2, 5 ]
数组第 2 次(第 k 次)右旋转的第 4 个(第 m 个)元素是 3。
输入
数组:[ 6, 8, 9 ], k: 1, 米:1
输出
9
解释:第一次右旋转:[ 9, 6, 8 ]
数组第一次(第 k 次)右旋转的第 1 个(第 m 个)元素为 9。
简单方法
这种方法的思路很简单，首先，我们计算给定数组的第 k 次右旋转，然后打印该右旋转数组的第 m 个元素。
让我们看下面的代码以更好地理解上述方法。
示例
C++ 程序用于在数组进行 K 次右旋转后查找第 M 个元素。
#include <bits/stdc++.h>
using namespace std;
// 数组左旋转ele
void leftRotation(int n, int array [], int ele){
reverse (array, array + ele);
reverse (array + ele, array + n);
reverse (array, array + n);
}
// 将数组右旋转 ele
void rightRotation(int n, int array [], int ele){
leftRotation(n, array, n - ele);
}
// 创建一个函数来查找第 m 个元素并返回它
int findMthElement(int n, int array [], int k, int m){
// 调用 rightRotation 函数将给定数组旋转 k 次
for (int i=1; i<=k; i++) {
rightRotation(n, array, 1);
}
// 返回右旋转 k 次后的最终第 m 个元素
return array[m - 1];
}
int main(){
int array [] = { 1, 3, 2, 5, 6, 7 }; //给定数组
int n = sizeof(array) / sizeof(array [0]); //获取数组的大小
int k = 2; //给定整数k
int m = 4; //给定整数m
int mthElement = findMthElement(n, array, k, m);
cout << "数组第k次右旋转后的第m个元素为:";
cout<< mthElement;
return 0;
}
输出
数组第 k 次右旋转后的第 m 个元素为:3
时间和空间复杂度
上述代码的时间复杂度为 O(n * k)，因为我们将大小为 n 的数组旋转了 k 次。
上述代码的空间复杂度为 O(1)，因为没有使用额外的空间。
数学方法
在这种方法中，我们使用了数学。数学的概念是数组与 n(数组大小)旋转后相同。因此，我们可以说第 k 次旋转与 k%n 次旋转相同。
因此，我们转换 k = k%n，现在我们确定 k 的大小小于 n(n 数组的大小)。
如果 m 大于等于 k，则答案为给定数组的 (n-k) + (m-1) 个元素。
如果 m 小于 k，则答案为给定数组的 (m-1-k) 个元素。
为了进一步理解上述方法，让我们看看下面的代码。
示例
C++ 程序在数组右旋转 K 次后查找第 M 个元素
#include <bits/stdc++.h>
using namespace std;
// 创建一个函数来查找第 m 个元素并返回它
int findMthElement(int n, int array [], int k, int m){
// 好像 k 大于数组 n 的大小
k = k % n;
// 创建 mthElementIndex 来存储第 m 个元素的索引
int MthElementIndex;
if (k < m) {
MthElementIndex = (m - k - 1);
} else {
MthElementIndex = (n - k) + (m - 1);
}
int mthElement = array [MthElementIndex]; // 存储最终答案
return mthElement;
}
int main (){
int array [] = { 1, 3, 2, 5, 6, 7 }; //给定数组
int n = sizeof(array) / sizeof(array [0]); //获取数组的大小
int k = 2; //给定整数 k
int m = 4; //给定整数 m
int mthElement = findMthElement(n, array, k, m);
cout << "数组第 k 次右旋转后的第 m 个元素为: ";
cout<<mthElement;
return 0;
}
输出
数组第 k 次右旋转后的第 m 个元素为:3
时间和空间复杂度
上述代码的时间复杂度为 O(1)。
上述代码的空间复杂度为 O(1)。
结论
在本教程中，我们实现了一个 C++ 程序来查找数组 K 次右旋转后的第 M 个元素。我们实现了两种方法:朴素方法和数学方法。时间复杂度分别为 O(n*k) 和 O(1)。其中 n 是数组的大小，k 是给定的 k 个整数。两种方法的空间复杂度均为 O(1)。
