資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學查詢陣列經 K 次右旋轉後的第 M 個元素
陣列右旋轉是指將陣列的元素向右移動一定數量的位置。在一次右旋轉中，陣列的最後一個元素成為第一個元素，其餘元素向右移動。
問題陳述
目標是在執行 K 次右旋轉後查詢陣列的第 M 個元素，其中 K 和 M 是非負整數，陣列包含 N 個元素。
示例
輸入
arr = [12 34 56 21], K = 2, M = 1
輸出
56
解釋
K 次右旋轉後的陣列 = [56 21 12 34]
第 1 個位置的元素 = 56
輸入
arr = [0 3 1 5 7 2 2], K = 6, M = 4
輸出
7
解釋
K 次右旋轉後的陣列 = [3 1 5 7 2 2 0]
第 4 個位置的元素 = 7
方法一
我們將要討論的解決方案將問題陳述視為兩個方面。這裡有兩個目標需要完成。它們如下所示：
將陣列右旋轉 K 次。
返回修改後陣列的第 M 個元素。
任務 1：可以使用內建的 reverse() 函式來實現。以下幹執行完美地演示了這一點。
設原始向量 arr 為 {1, 2, 3, 4, 5}
設右旋轉次數 (K) 為 2
原始 arr
| 1 | 2 | 3 | 4 | 5 |
反轉 arr 的最後 K 個元素
| 1 | 2 | 3 | 5 | 4 |
反轉 arr 的前 N - K 個元素
| 3 | 2 | 1 | 5 | 4 |
現在反轉整個 arr
| 4 | 5 | 1 | 2 | 3 |
因此，在執行 3 次反轉操作後，我們得到 arr 右旋轉 K 次。
任務 2：現在要查詢第 M 個元素，我們只需返回 arr 中 (M - 1) 索引處的元素，因為我們遵循基於 0 的索引。
虛擬碼
函式 rightRotateByk(arr, k)
反轉(最後 K 個元素)
反轉(前 N - K 個元素)
反轉(所有元素)
結束函式
函式 solve(arr, k, m)
rightRotateByk(arr, k)
返回 arr[m - 1]
結束函式
函式 main()
定義 arr[ ]
初始化 k
初始化 m
宣告 ans
函式呼叫 solve(arr, k, m)
將結果儲存在 ans 中
輸出 ans
結束函式
示例：C++ 程式
程式碼確定在對原始陣列進行 K 次右旋轉後第 M 個位置的元素。定義 rightRotateByk() 函式以順時針方式旋轉陣列 arr K 次。在 rightRotateByk 函式內部，執行三個反轉操作
使用範圍 (arr.begin() + arr.size() - k, arr.end()) 反轉 arr 的最後 K 個元素。
使用範圍 (arr.begin(), arr.begin() + arr.size() - k) 反轉 arr 的初始元素（不包括最後 K 個元素）。
反轉 arr 的所有元素以完成右旋轉。
透過訪問 arr[m - 1] 返回旋轉後陣列的第 M 個元素，因為陣列索引從 0 開始。
示例
// C++ program to determine the element at the Mth number after subjecting the original array to k right rotations
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
// Function to rotate arr K times in clockwise manner
void rightRotateByk(vector<int> &arr, int k){
// reverse the last K elements
reverse(arr.begin() + arr.size() - k, arr.end());
// reverse the initial elements other than the last k elements
reverse(arr.begin(), arr.begin() + arr.size() - k);
// reverse all the elements to right rotate the original arr K times
reverse(arr.begin(), arr.end());
}
// Function to return the Mth element of arr after subjecting arr to K right rotations
int solve(vector<int> &arr, int k, int m){
rightRotateByk(arr, k);
// Return the Mth element of arr
return arr[m - 1];
}
int main(){
vector<int> arr = {5, 7, 2, 8, 0};
int k, m;
k = 2;
m = 2;
int ans = solve(arr, k, m);
cout << "Mth element after K right rotations is: " << ans << endl;
return 0;
}
輸出
Mth element after K right rotations is: 0
時間和空間複雜度分析
時間複雜度：O(n)
rightRotateByk 函式執行三個反轉操作，每個操作都需要線性時間。因此，rightRotateByk 的時間複雜度為 O(n)，其中 n 是陣列的大小。
此外，訪問陣列的第 M 個元素需要常數時間。
空間複雜度：O(1)
程式碼除了用於儲存輸入陣列的向量外，沒有使用任何輔助空間。
方法二
一個簡單的見解可以極大地最佳化程式碼。關鍵觀察是，經過 N 次旋轉後，原始陣列將被恢復，因為元素會環繞回到其原始位置。基於此觀察，我們可以使用模運算子 % 來確定有效的旋轉次數。
對於任何正整數 K，K%N 將產生 0 到 N-1 範圍內的值。
如果 K 大於或等於 M (K >= M)，則表示原始陣列中的第 M 個元素位於 K 次右旋轉的部分內。在這種情況下，我們將原始陣列中第 M 個元素的索引計算為 (N - K) + (M - 1)。
(N - K) 表示透過 K 次旋轉向右移動的元素數量。
(M - 1) 表示移位部分內的索引偏移量。
如果 K 小於 M (K < M)，則表示原始陣列中的第 M 個元素位於右旋轉後開頭處剩餘的部分內。在這種情況下，我們將原始陣列中第 M 個元素的索引計算為 (M - K - 1)。
(M - K - 1) 表示陣列開頭剩餘部分中元素的索引。
示例：C++ 程式
程式碼確定執行 K 次右旋轉後陣列的第 M 個元素。它透過使用模運算子來處理 K 超過陣列大小的情況。根據 K 和 M 之間的關係計算第 M 個元素的索引。最後，它返回旋轉後原始陣列中該索引處的元素。
示例
// C++ program to determine the element at the Mth number after subjecting the original array to k right rotations
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to return the Mth element if the original array is subjected to K right rotations
int solve(vector<int> arr, int K, int M){
int N = arr.size();
// (K % N) will yield a value in the range of 0 to N-1
K %= N;
int ind;
if (K >= M) {
// This implies that the Mth element in the original array is within the K right-rotated portion
ind = (N - K) + (M - 1);
}
else{
// This means that the Mth element in the original array is within the portion that remains at the beginning after the right rotations.
ind = (M - K - 1);
}
return arr[ind];
}
int main(){
vector<int> arr = {0, 3, 1, 5, 7, 2, 2};
int k, m;
k = 6;
m = 4;
int ans = solve(arr, k, m);
cout << "Mth element after K right rotations is: " << ans << endl;
return 0;
}
輸出
Mth element after K right rotations is: 7
時間和空間複雜度分析
程式在常數時間內執行，不需要輔助空間。因此程式的時間和空間複雜度為 O(1)。
結論
本文討論了兩種方法來返回陣列的第 M 個元素，如果將其右旋轉 K 次。它提供了 C++ 程式程式碼、虛擬碼以及時間和空間複雜度分析。
73 次瀏覽
