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

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

给定非负整数 KM 和由 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 个元素。

算法:

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

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;
}  

输出

4

时间复杂度: 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;
}  

输出:

4

时间复杂度: O(1)

辅助空间: O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例