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)。