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

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

给定非负整数 KM ,以及包含 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 的元素。

  1. 数组在经过 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)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例