C++程序寻找数组右旋K次后第M个元素

给定非负整数 K 、 M 和由 N 个元素组成的数组 arr[] ，任务是在将数组右旋 K 次后找到第 **M th ** 个元素。

示范：

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

输出： 5

解释：

第一次右旋之后的数组 a1[] = {23, 3, 4, 5}

第二次右旋之后的数组 a2[] = {5, 23, 3, 4}

2次右旋后的第1个元素是5。

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

输出： 4

解释：

数组进行了3次右旋，第2个位置上是4。

Naive Approach:

最简单的解决方法是先将数组右旋 K 次，然后再找到旋转后第 **M th 个元素。

算法：

定义一个名为 leftrotate 的函数，它将一个 vector 和一个整数 d 作为输入。该函数应该将向量的元素从开始位置到索引 d 反转，然后从索引 d 到末尾，最后整个向量。
定义一个名为 rightrotate 的函数，它将一个 vector 和一个整数 d 作为输入。该函数应该使用向量和向量大小与 d 的差异作为参数调用 leftrotate。
定义一个名为 getFirstElement 的函数，它将一个整数数组 a 、其大小 N 和两个整数 K 和 M 作为输入。该函数应该执行以下操作：

a. 使用数组 a 中的元素初始化一个向量 v。

b. 循环 K 次，每次调用带有向量和整数值 1 作为参数的 rightrotate 以将向量 v 向右旋转 K 次。
c. 返回旋转后向量 v 的第 M 个元素。

4. 在主函数中，使用适当的值初始化一个整数数组 a、其大小 N 和两个整数 K 和 M。

5. 调用函数 getFirstElement ，并将数组 a、N、K 和 M 作为参数，打印返回的值。

下面是解决方案的实现：

// C++程序，用于找到K次右旋后数组中的第M个元素。

#include 
using namespace std;

// 将数组in-place左旋转d次
void leftrotate(vector& v, int d)
{
    reverse(v.begin(), v.begin() + d);
    reverse(v.begin() + d, v.end());
    reverse(v.begin(), v.end());
}

// 将数组in-place右旋转d次
void rightrotate(vector& v, int d)
{
    leftrotate(v, v.size() - d);
}

// 返回K次右旋后数组中的第M个元素
int getFirstElement(int a[], int N, int K, int M)
{
    vector v;

    for (int i = 0; i < N; i++)
        v.push_back(a[i]);

    // 右旋转K次
    while (K--) {
        rightrotate(v, 1);
    }

    // 返回第M个元素
    return v[M - 1];
}

// 主函数
int main()
{
    // 初始化数组
    int a[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(a) / sizeof(a[0]);
    int K = 3, M = 2;

    // 调用函数
    cout << getFirstElement(a, N, K, M);

    return 0;
}

输出

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

辅助空间： O(N)

高效做法：

为了优化这个问题，需要进行以下观察：

如果数组旋转 N 次，则返回原始数组。

例如，a[]= {1,2,3,4,5}，K=5 5次右旋后修改后的数组a5[] = {1,2,3,4,5}。

因此，在进行 K 次旋转后，数组中的元素是原始数组中的 K％N 号元素。
如果 K≥M ，则在K次右旋转后数组中的第M个元素是在原始数组中的第 {(N-K)+(M-1)} 个元素。
如果 K <M，则在K次右旋转后数组中的第M个元素是在原始数组中的第 (M-K-1) 个元素。

以下是上述方法的实现：

// C++程序，用于实现上述算法
#include
using namespace std;

// 返回K次右旋后数组中的第M个元素
int getFirstElement(int a[], int N,
                                    int K, int M)
{
    // 数组在N次旋转后恢复到原始状态
    K %= N;
    int index;

    // 如果K>=M
    if (K >= M)

        // 在K次右旋转后，数组中第M个元素是原始数组中第(N-K)+(M-1)个元素。
        index = (N - K) + (M - 1);

    // 否则
    else

        // 在K次右旋转后，数组中第M个元素是原始数组中第(M-K-1)个元素。
        index = (M - K - 1);

    int result = a[index];

    // 返回结果
    return result;
}

// 主函数
int main()
{
    int a[] = { 1, 2, 3, 4, 5 };

    int N =sizeof(a) / sizeof(a[0]);

    int K = 3, M = 2;

    cout << getFirstElement(a, N, K, M);

    return 0;
}

输出：

时间复杂度： O(1)

辅助空间： O(1)