数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：查找数组经过K次左移后的第M个元素
在这个问题中，我们需要在数组经过K次旋转后打印给定索引处的元素。
这个问题教会我们如何在旋转后的数组中找到特定索引处的元素。乍一看，想到的解决方案是将数组旋转K次，然后访问第M个元素，但我们还将学习如何在不旋转数组的情况下访问旋转数组中的第M个元素。
问题陈述
我们给定一个包含N个数字的数组arr[]。此外，我们还给定了正整数M和K。我们需要将arr[]数组左移旋转K次，并返回数组的第M个元素。
示例
Input – arr[] = {10, 12, 34, 3, 7, 6}, K = 3, M = 2
Output – 7
解释
让我们先将数组旋转3次。
第一次旋转后，数组为{12, 34, 3, 7, 6, 10}。
第二次旋转后，数组为{34, 3, 7, 6, 10, 12}。
最终旋转后的更新数组为{3, 7, 6, 10, 12, 34}。
因此，更新数组中的第2个元素是7。
Input – arr[] = {76, 43, 4, 5, 9, 69, 12, 54}, K = 0, M = 5
Output – 9
解释
由于K为0，我们不需要旋转数组。因此，原始数组中的第5个元素是9。
Input – arr[] = {76, 43, 4, 5, 9, 69, 12, 54}, K = 10, M = 3
Output – 9
解释
经过10次旋转后的最终数组为{4, 5, 9, 69, 12, 54, 76, 43}。因此，更新数组中的第3个元素是9。
方法1
在这种方法中，我们将对数组元素进行K次交换，将其与下一个元素交换，并将第一个元素与最后一个元素交换，以将数组旋转K次。
之后，我们将从所需的索引访问数组元素。
算法
步骤1 - 使用循环进行总共K次迭代。
步骤2 - 使用'temp'变量存储arr[q]元素。
步骤3 - 之后，用arr[q + 1]元素更新arr[q]。
步骤4 - 接下来，用temp元素更新arr[q + 1]。
步骤5 - 从M – 1索引返回数组元素。
示例
#include <bits/stdc++.h>
using namespace std;
int arr_rotation(int arr[], int arr_len, int K, int M) {
// Rotate array by K left rotations
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;
}
}
// Return element from M index
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) {
// Take modulo of K with arr_len
K %= arr_len;
// Get Mth element
int ind = (K + M - 1) % arr_len;
int ele = arr[ind];
// return element
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 << "The array element after " << K << " rotation at the " << M << " index is " << arr_rotation(arr, arr_len, K, M);
return 0;
}
输出
The array element after 3 rotation at the 2 index is 7
时间复杂度 - O(1)
空间复杂度 - O(1)
我们学习了如何在进行K次左移旋转后访问第M个元素。程序员可以尝试在进行K次右移旋转后访问第M个元素，或者在进行K次右移旋转后访问第(N – M)个元素。
68 次查看
