C++程序查找数组K次右移后的第M个元素

---

右移意味着我们将每个元素向右移动，例如第0个索引的元素移动到第1个索引，第1个索引的元素移动到第2个索引，以此类推，最后一个元素移动到第0个索引。这里我们给定一个大小为n的整数数组，整数m和整数k。我们的任务是在数组进行k次右移后找到第m个元素。

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

示例

输入

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

输出

3

解释：第1次右移：[ 7, 1, 3, 2, 5, 6 ]

第2次右移：[ 6, 7, 1, 3, 2, 5 ]

数组进行2次（k）右移后的第4个（m）元素是3。

输入

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

输出

9

解释：第1次右移：[ 9, 6, 8 ]

数组进行1次（k）右移后的第1个（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 = 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是给定的整数k。两种方法的空间复杂度均为O(1)。