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值計算最終索引值，使問題解決方案更高效。