C++ 程序在 K 次左旋转后查找数组的第 M 个元素
在这个问题中，我们需要在将数组旋转 K 次后从给定索引打印元素。
这个问题教我们从旋转数组中的特定索引中找到元素。乍一看，想到的解决方案是将数组旋转 K 次并访问第 M 个元素，但我们还将学习如何在不旋转数组的情况下访问旋转数组中的第 M 个元素。
问题陈述
我们给出了包含 N 个数字的 arr[] 数组。另外，我们给出了正整数 M 和 K。我们需要将 arr[] 数组左旋转 K 次，并返回数组的第 M 个元素。
示例
输入 – arr[] = {10, 12, 34, 3, 7, 6}, K = 3, M = 2
输出 – 7
解释
我们先将数组旋转 3 次。
第一次旋转后，数组为 {12, 34, 3, 7, 6, 10}。
第二次旋转后，数组为 {34, 3, 7, 6, 10, 12}旋转。
最终旋转后更新的数组为 {3, 7, 6, 10, 12, 34}。
因此，更新后的数组中的第 2 个元素为 7。
输入 – arr[] = {76, 43, 4, 5, 9, 69, 12, 54}, K = 0, M = 5
输出 – 9
解释
我们不需要旋转数组，因为 K 为 0。因此，原始数组中的第 5 个元素为 9。
输入 – arr[] = {76, 43, 4, 5, 9, 69, 12, 54}, K = 10, M = 3
输出 – 9
解释
经过 10 次旋转后的最终数组为 {4, 5, 9, 69, 12, 54, 76, 43}。因此，更新后的数组中的第 3 个元素是 9。
方法 1
在此方法中，我们将所有数组元素与其下一个元素交换 K 次，并将第一个元素与最后一个元素交换，以将数组旋转 K 次。
之后，我们将从所需索引访问数组元素。
算法
步骤 1 - 使用循环进行总共 K 次迭代。
步骤 2 - 使用 arr[q] 元素初始化"temp"变量。
步骤 3 - 之后，使用 arr[q + 1] 元素更新 arr[q]。
步骤 4 - 接下来，更新 arr[q + 1] 与 temp 元素。
步骤 5 − 从 M – 1 索引返回数组元素。
示例
#include <bits/stdc++.h>
using namespace std;
int arr_rotation(int arr[], int arr_len, int K, int M) {
// 对数组进行 K 次左旋转
for (int p = 0; p < K; p++) {
for (int q = 0; q < arr_len - 1; q++) {
int temp = arr[q];
arr[q] = arr[q + 1];
arr[q + 1] = temp;
}
}
// 返回 M 索引中的元素
return arr[M - 1];
}
int main() {
int arr[] = {10, 12, 34, 3, 7, 6};
int arr_len = sizeof(arr) / sizeof(arr[0]);
int K = 3, M = 2;
cout << "The array element after " << K << " rotations at the " << M << " index is " << arr_rotation(arr, arr_len, K, M);
return 0;
}
输出
The array element after 3 rotations at the 2 index is 7
时间复杂度 − O(N*K)，其中 N 是数组长度，K 是左旋转的总数。
空间复杂度− O(1)，因为我们使用常数空间。
方法 2
如果我们将数组旋转 K 次，则第 K 个(基于 0 的索引)将成为数组的第一个索引。如果 K 大于数组长度，我们需要通过对数组长度取模使其小于数组长度。
之后，我们可以从旋转数组中的第 K 个索引访问第 (M - 1) 个元素。
算法
步骤 1 - 对 K 执行数组长度的模运算。
步骤 2 - 将 '(K + M - 1) % arr_len' 的结果值存储到 'ind' 变量中。
步骤 3 - 从 'ind' 索引访问数组元素并将其存储在 'ele' 变量中。
步骤 4 - 返回 'ele' 变量的值。
示例
#include <bits/stdc++.h>
using namespace std;
int arr_rotation(int arr[], int arr_len, int K, int M) {
// 对 K 和 arr_len 取模
K %= arr_len;
// 获取第 M 个元素
int ind = (K + M - 1) % arr_len;
int ele = arr[ind];
// 返回元素
return ele;
}
int main() {
int arr[] = {10, 12, 34, 3, 7, 6};
int arr_len = sizeof(arr) / sizeof(arr[0]);
int K = 3, M = 2;
cout << "在索引为" << M << "处，经过" << K << "旋转后的数组元素为" << arr_rotation(arr, arr_len, K, M);
return 0;
}
输出
在索引为 2 处，经过 3 次旋转后的数组元素为 7
时间复杂度 − O(1)
空间复杂度 − O(1)
我们学会了在进行 K 次左旋转后访问第 M 个元素。程序员可能会尝试在进行 K 次右旋转后访问第 M 个元素，或者在进行 K 次右旋转后访问第 (N – M) 个元素。
