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 作为参数,打印返回的值。
下面是解决方案的实现:
输出
时间复杂度: 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) 个元素。
以下是上述方法的实现:
输出:
时间复杂度: O(1)
辅助空间: O(1)