C++ 在数组经过K次右旋转之后找到第M个元素的C++程序

右旋转意味着我们需要将每个元素向右移动，第0个索引元素移动到第1个索引，第1个索引元素移动到第2个索引，依此类推，而最后一个元素移动到第0个索引。在这里，我们有一个大小为n的整数数组，整数m和整数k。我们的任务是在对数组进行k次右旋转之后找到第m个元素。

以下是一些示例和解释，以帮助您理解问题。

示例例子

输入

Array: [ 1, 3, 2, 5, 6, 7 ],
k: 2,
m: 4

输出

3

解释 ：第一次向右旋转：[ 7, 1, 3, 2, 5, 6 ]

第二次向右旋转：[ 6, 7, 1, 3, 2, 5 ]

数组的第二次右旋转的第四个元素是3。

输入

Array: [ 6, 8, 9 ],
k: 1,
m: 1

输出

9

说明 ：第1次右旋转：[9, 6, 8]

第k次右旋转中的第m个元素是9。

本地方法

这种方法的思路很简单，首先计算给定数组的第k次右旋转，然后打印右旋转后数组的第m个元素。

让我们看看下面的代码以更好地理解上述方法。

示例

C++程序：查找数组右旋转k次之后的第m个元素。

#include <bits/stdc++.h>
using namespace std;

// left rotation of an array by ele
void leftRotation(int n, int array [], int ele){
   reverse (array, array + ele);
   reverse (array + ele, array + n);
   reverse (array, array + n);
}
// right rotation of an array by ele
void rightRotation(int n, int array [], int ele){
   leftRotation(n, array, n - ele);
}
// Create a function to find mth element and return it
int findMthElement(int n, int array [], int k, int m){
   // Call the rightRotation function to rotate given array k times
    for (int i=1; i<=k; i++) {
        rightRotation(n, array, 1);
    }
   // return the final mth element after k right rotation
   return array[m - 1];
}
int main(){
   int array [] = { 1, 3, 2, 5, 6, 7 }; //Given array
   int n = sizeof(array) / sizeof(array [0]); //Getting the size of the array
   int k = 2; //Given integer k
   int m = 4; //Given integer m
   int mthElement = findMthElement(n, array, k, m);
   cout << "mth element after the kth right rotation of an array is: ";
   cout<< mthElement;
   return 0;
}

输出

mth element after the kth right rotation of an array is: 3

时间和空间复杂度

上述代码的时间复杂度是O(n * k)，因为我们将一个大小为n的数组旋转了k次。

上述代码的空间复杂度是O(1)，因为没有使用额外的空间。

数学方法

在这种方法中，我们使用了数学。数学的概念是，数组在经过n（数组的大小）次旋转后仍然是相同的。因此，我们可以说第k次旋转与第k%n次旋转相同。

因此，我们将k = k%n进行转换，现在我们可以确保k的大小小于数组n的大小。

如果m大于等于k，则答案是给定数组的（n-k）+（m-1）个元素。

如果m小于k，则答案是给定数组的（m-1-k）个元素。

为了进一步理解上述方法，让我们看一下下面的代码。

示例

C++程序，找到经过k次右旋转后的数组的第m个元素。

#include <bits/stdc++.h>
using namespace std;

 // Create a function to find mth element and return it
int findMthElement(int n, int array [], int k, int m){
   // as if k is greater than the size of array n
   k = k % n; 
   // Create the mthElementIndex to store the index of mth element
   int MthElementIndex;
   if (k < m) {
      MthElementIndex = (m - k - 1);
   } else {
      MthElementIndex = (n - k) + (m - 1);
   }
   int mthElement = array [MthElementIndex]; // store the final answer
   return mthElement;
}
int main (){   
   int array [] = { 1, 3, 2, 5, 6, 7 }; //Given array
   int n = sizeof(array) / sizeof(array [0]); //Getting the size of the array
   int k = 2; //Given integer k
   int m = 4; //Given integer m
   int mthElement = findMthElement(n, array, k, m);
   cout << "mth element after the kth right rotation of an array is: ";
   cout<<mthElement;
   return 0;
}

输出

mth element after the kth right rotation of an array is: 3

时间和空间复杂度

上述代码的时间复杂度是O(1)。

上述代码的空间复杂度是O(1)。

结论

在本教程中，我们实现了一个C++程序来找到一个数组经过K次右旋后的第M个元素。我们实现了两种方法，分别是朴素方法和数学方法。时间复杂度分别为O(n*k)和O(1)，其中n是数组的大小，k是给定的整数。这两种方法的空间复杂度均为O(1)。