Java 程序在 K 次左旋转后查找数组的第 M 个元素
在此问题中，我们将对数组进行 K 次左旋转，并在旋转后的数组中找到第 M 个元素。
解决该问题的简单方法是对数组进行 K 次左旋转，并从 M – 1 索引中取出元素。
优化方法是找到最终索引值，使得最终索引是旋转后的数组的 M – 1 索引。
问题陈述
我们给出了一个包含正整数的 nums[] 数组。我们还给出了正整数 K 和 M。我们需要对数组进行 K 次左旋转，并打印第 M 个元素。
示例
输入 – nums[] = { 20, 30, 5, 6, 8, 23 }; K = 3, M = 3;
输出 – 23
解释
第一次旋转后，数组变为 {30, 5, 6, 8, 23, 20}。
第二次旋转后，更新后的数组为 {5, 6, 8, 23, 20, 30}。
最后一次旋转后，数组为 {6, 8, 23, 20, 30, 5}。
最终数组中第 3 位的元素为 23。
输入 – nums[] = { 20, 30, 5, 6, 8, 23 }; K = 0, M = 3;
输出 – 5
解释
我们需要进行 0 次旋转。因此，原始数组中第 3 个位置的元素是 5。
输入 – nums[] = { 20, 30, 5, 6, 8, 23 }; K = 5, M = 2;
输出 – 20
解释
5 次左旋转后的数组将为 {23, 20, 30, 5, 6, 8}，更新后的数组中的第 2 个元素为 20。
方法 1
在此方法中，我们将通过 K 次左旋转来旋转数组。之后，我们将从数组的 M – 1 索引访问元素。
算法
步骤 1 - 开始遍历数组。
步骤 2 - 将第一个数组元素存储在"temp"变量中。
步骤 3 - 使用另一个嵌套循环遍历数组。在嵌套循环中，将 nums[q] 替换为 nums[q + 1]。
步骤 4 - 在外循环内，将 nums[nums_len – 1] 替换为"temp"值。
步骤 5 - 返回 nums[M – 1] 元素。
示例
import java.util.*;
public class Main {
public static int findElement(int[] nums, int nums_len, int K, int M){
// 对数组进行 K 次左旋转
for (int p = 0; p < K; p++) {
int temp = nums[0];
for (int q = 0; q < nums_len - 1; ++q) {
nums[q] = nums[q + 1];
}
nums[nums_len - 1] = temp;
}
// 返回旋转数组的第 M 个元素
return nums[M-1];
}
public static void main(String[] args) {
int nums[] = { 20, 30, 5, 6, 8, 23 };
int nums_len = nums.length;
int K = 3, M = 3;
System.out.println("The element at " + M + " index after rotating array by " + K + " left rotations is "
+ findElement(nums, nums_len, K, M));
}
}
输出
将数组左旋转 3 次后，索引 3 处的元素为 23
时间复杂度 - O(N*K) 进行 K 次左旋转。
空间复杂度 - O(1)，因为我们不使用任何动态空间。
方法 2
在此方法中，我们将对 K 取数组长度的模数。因为如果我们进行左旋转，使其等于数组的长度，我们就会得到原始数组。
如果我们对数组进行 K 次旋转，我们会在第一个位置得到第 (K – 1) 个元素，然后从那里，我们需要取出第 M 个元素。
算法
步骤 1 - 对数组长度取 K 的模数。
步骤 2 - 将对数组长度取 (K + M – 1) 的模数后的结果值存储到"ind"变量中。
步骤 3 - 从"ind"索引访问数组元素，并返回其值。
示例
import java.util.*;
public class Main {
public static int findElement(int[] nums, int nums_len, int K, int M) {
K %= nums_len;
// 获取第 M 个元素的索引
int ind = (K + M - 1) % nums_len;
return nums[ind];
}
public static void main(String[] args) {
int nums[] = { 20, 30, 5, 6, 8, 23 };
int nums_len = nums.length;
int K = 3, M = 3;
System.out.println("将数组左旋转 " + K + " 次后，索引 " + M + " 处的元素为 "
+ findElement(nums, nums_len, K, M));
}
}
输出
将数组左旋转 3 次后，索引 3 处的元素为 23
时间复杂度 − O(1)，因为我们不遍历数组。
空间复杂度 − O(1)，因为我们使用常量空间。
结论
第一种方法将数组旋转 K 次，但第二种方法根据给定的 K 和 M 值计算最终索引值，从而使问题解决更加高效。
