資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢陣列經過K次左移後的第M個元素
在這個問題中，我們需要在陣列經過K次旋轉後列印給定索引處的元素。
這個問題教會我們如何在旋轉後的陣列中找到特定索引處的元素。乍一看，想到的解決方案是將陣列旋轉K次，然後訪問第M個元素，但我們還將學習如何在不旋轉陣列的情況下訪問旋轉陣列中的第M個元素。
問題陳述
我們給定一個包含N個數字的陣列arr[]。此外，我們還給定了正整數M和K。我們需要將arr[]陣列左移旋轉K次，並返回陣列的第M個元素。
示例
Input – arr[] = {10, 12, 34, 3, 7, 6}, K = 3, M = 2
Output – 7
解釋
讓我們先將陣列旋轉3次。
第一次旋轉後，陣列為{12, 34, 3, 7, 6, 10}。
第二次旋轉後，陣列為{34, 3, 7, 6, 10, 12}。
最終旋轉後的更新陣列為{3, 7, 6, 10, 12, 34}。
因此，更新陣列中的第2個元素是7。
Input – arr[] = {76, 43, 4, 5, 9, 69, 12, 54}, K = 0, M = 5
Output – 9
解釋
由於K為0，我們不需要旋轉陣列。因此，原始陣列中的第5個元素是9。
Input – arr[] = {76, 43, 4, 5, 9, 69, 12, 54}, K = 10, M = 3
Output – 9
解釋
經過10次旋轉後的最終陣列為{4, 5, 9, 69, 12, 54, 76, 43}。因此，更新陣列中的第3個元素是9。
方法1
在這種方法中，我們將對陣列元素進行K次交換，將其與下一個元素交換，並將第一個元素與最後一個元素交換，以將陣列旋轉K次。
之後，我們將從所需的索引訪問陣列元素。
演算法
步驟1 - 使用迴圈進行總共K次迭代。
步驟2 - 使用'temp'變數儲存arr[q]元素。
步驟3 - 之後，用arr[q + 1]元素更新arr[q]。
步驟4 - 接下來，用temp元素更新arr[q + 1]。
步驟5 - 從M – 1索引返回陣列元素。
示例
#include <bits/stdc++.h>
using namespace std;
int arr_rotation(int arr[], int arr_len, int K, int M) {
// Rotate array by K left rotations
for (int p = 0; p < K; p++) {
for (int q = 0; q < arr_len - 1; q++) {
int temp = arr[q];
arr[q] = arr[q + 1];
arr[q + 1] = temp;
}
}
// Return element from M index
return arr[M - 1];
}
int main() {
int arr[] = {10, 12, 34, 3, 7, 6};
int arr_len = sizeof(arr) / sizeof(arr[0]);
int K = 3, M = 2;
cout << "The array element after " << K << " rotations at the " << M << " index is " << arr_rotation(arr, arr_len, K, M);
return 0;
}
輸出
The array element after 3 rotations at the 2 index is 7
時間複雜度 - O(N*K)，其中N是陣列長度，K是左移旋轉的總次數。
空間複雜度 - O(1)，因為我們使用了常數空間。
方法2
如果我們將陣列旋轉K次，則第K個（基於0的索引）將成為陣列的第一個索引。如果K大於陣列長度，我們需要透過將其取模陣列長度使其小於陣列長度。
之後，我們可以從旋轉陣列中的第K個索引訪問第(M - 1)個元素。
演算法
步驟1 - 對K執行模陣列長度運算。
步驟2 - 將'(K + M - 1) % arr_len'的結果值儲存到'ind'變數中。
步驟3 - 從'ind'索引訪問陣列元素並將其儲存到'ele'變數中。
步驟4 - 返回'ele'變數的值。
示例
#include <bits/stdc++.h>
using namespace std;
int arr_rotation(int arr[], int arr_len, int K, int M) {
// Take modulo of K with arr_len
K %= arr_len;
// Get Mth element
int ind = (K + M - 1) % arr_len;
int ele = arr[ind];
// return element
return ele;
}
int main() {
int arr[] = {10, 12, 34, 3, 7, 6};
int arr_len = sizeof(arr) / sizeof(arr[0]);
int K = 3, M = 2;
cout << "The array element after " << K << " rotation at the " << M << " index is " << arr_rotation(arr, arr_len, K, M);
return 0;
}
輸出
The array element after 3 rotation at the 2 index is 7
時間複雜度 - O(1)
空間複雜度 - O(1)
我們學習瞭如何在進行K次左移旋轉後訪問第M個元素。程式設計師可以嘗試在進行K次右移旋轉後訪問第M個元素，或者在進行K次右移旋轉後訪問第(N – M)個元素。
68 次檢視
