C++程序 在K次左旋转后查找数组中第M个元素

给定非负整数 K 、 M ，以及包含 N 个元素的数组 arr[] ，请找出数组在执行 K 次左旋转之后的 **第M th ** 个元素。

例子：

输入: arr[] = {3, 4, 5, 23}，K = 2，M = 1

输出: 5

解释:

第一次左旋转之后，数组为 1 [ ] = {4, 5, 23, 3}

第二次左旋转之后，数组为 2 [ ] = {5, 23, 3, 4}

在进行2次左旋转后的第1个元素为5。

输入: arr[] = {1, 2, 3, 4, 5}，K = 3，M = 2

输出: 5

解释:

3次左旋转后，第2个位置上有数字5。

暴力法: 对于这个问题的想法是执行 K 次左旋转操作，然后找到最终数组的第 **M th ** 个元素。

时间复杂度: O(N * K)

辅助空间: O(N)

高效做法: 优化问题时，请注意以下几点：

1. 如果数组旋转了 N 次，它就会返回初始数组。例如，a[ ] = {1, 2, 3, 4, 5}，K=5，那么进行5次左旋转后，数组为 5 [ ] = {1, 2, 3, 4, 5}.

因此，在进行 K 次旋转之后的数组元素是原始数组中索引为 K%N 的元素。

2. 数组在经过 K 次左旋转后的第

{ (K + M – 1) % N }th

在原始数组中的位置是

下面是上述方法的实现：
“`cpp // C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 

<pre><code>// Function to return Mth element of 
// array after k left rotations 
int getFirstElement(int a[], int N, 
                    int K, int M) 
{ 
    // The array comes to original state 
    // after N rotations 
    K %= N; 

    // Mth element after k left rotations 
    // is (K+M-1)%N th element of the 
    // original array 
    int index = (K + M – 1) % N; 

    int result = a[index]; 

    // Return the result 
    return result; 
} 

// Driver Code 
int main() 
{ 
    // Array initialization 
    int a[] = { 3, 4, 5, 23 }; 

    // Size of the array 
    int N = sizeof(a) / sizeof(a[0]); 

    // Given K rotation and Mth element 
    // to be found after K rotation 
    int K = 2, M = 1; 

    // Function call 
    cout << getFirstElement(a, N, K, M); 
    return 0; 
}
</code></pre>

“`

输出:
cpp 5

时间复杂度: O(1)

辅助空间: O(1)