Java程序：查找数组左旋转K次后的第M个元素

---

在这个问题中，我们将对数组进行K次左旋转，并找到旋转后数组中的第M个元素。

解决这个问题的简单方法是对数组进行K次左旋转，然后从M-1索引处获取元素。

优化的解决方法是找到最终索引值，使得最终索引是旋转后数组的M-1索引。

问题陈述

我们给定一个包含正整数的nums[]数组。我们还给定正整数K和M。我们需要将数组左旋转K次并打印第M个元素。

示例

Input –  nums[] = { 20, 30, 5, 6, 8, 23 }; K = 3, M = 3;
Output – 23

解释

• 第一次旋转后，数组变为{30, 5, 6, 8, 23, 20}。

• 第二次旋转后，更新后的数组为{5, 6, 8, 23, 20, 30}。

• 最终旋转后，数组为{6, 8, 23, 20, 30, 5}。

最终数组中第3个位置的元素是23。

Input –  nums[] = { 20, 30, 5, 6, 8, 23 }; K = 0, M = 3;
Output – 5

解释

我们不需要进行旋转。因此，原始数组中第3个位置的元素是5。

Input –  nums[] = { 20, 30, 5, 6, 8, 23 }; K = 5, M = 2;
Output – 20

解释

左旋转5次后的数组将是{23, 20, 30, 5, 6, 8}，更新后数组中的第2个元素是20。

方法1

在这种方法中，我们将数组左旋转K次。之后，我们将访问数组中M-1索引处的元素。

算法

• 步骤1 − 开始遍历数组。

• 步骤2 − 将第一个数组元素存储到'temp'变量中。

• 步骤3 − 使用另一个嵌套循环遍历数组。在嵌套循环中，用nums[q+1]替换nums[q]。

• 步骤4 − 在外循环中，用'temp'值替换nums[nums_len - 1]。

• 步骤5 − 返回nums[M - 1]元素。

示例

import java.util.*;

public class Main {
   public static int findElement(int[] nums, int nums_len, int K, int M){
      // Making K left rotations of array
      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;
      }
      // Return Mth element of rotated array
      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));
   }
}

输出

The element at 3 index after rotating array by 3 left rotations is 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;
      // Get the index of the Mth element
      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("The element at " + M + " index after rotating array by " + K + " left rotations is "
      + findElement(nums, nums_len, K, M));
   }
}

输出

The element at 3 index after rotating array by 3 left rotations is 23

• 时间复杂度 − O(1)，因为我们没有遍历数组。

• 空间复杂度 − O(1)，因为我们使用了常量空间。

结论

第一种方法旋转数组K次，但第二种方法根据给定的K和M值计算最终索引值，使问题解决方案更高效。