資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 實現陣列右移的反轉演算法
在本文中，我們將瞭解如何使用反轉演算法將給定陣列向右旋轉 k 個元素，例如 -
Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
Output : { 43, 7, 3, 7, 4, 6, 2, 6 }
Explanation : Rotating each element of array by 4-element to the right gives { 43, 7, 3, 7, 4, 6, 2, 6 }.
Input : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
Output : { 4, 9, 3, 8, 5, 8, 2, 1 }解決方法
您可以透過將每個元素向右移動並重復此過程 k 次來輕鬆解決此問題。但是，這將花費更多時間，因為其時間複雜度將為 O(k * N)。
反轉演算法：反轉會反轉陣列，並且可以透過反轉一些元素範圍來完成陣列旋轉。根據此演算法 -
- 首先，反轉整個陣列。
- 使用 k 對 N（陣列大小）取模來修改 k，因為 k 大於 N。
- 反轉陣列的前 k 個元素以使其按順序排列。
- 然後反轉剩餘元素的範圍，即從 k 到 N-1。
示例
using namespace std;
#include <bits/stdc++.h>
void reverse(int nums[], int start,int end) {
int temp=0;
// reversing array with swapping start element with end element.
while(start<=end){
temp=nums[end];
nums[end]=nums[start];
nums[start]=temp;
start++;
end--;
}
}
int main() {
int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 };
int N = sizeof(arr)/sizeof(arr[0]);
int k = 4;
// reversing whole array
reverse(arr, 0, N-1);
k = k%N;
// reversing element range of 0 to k-1.
reverse(arr, 0, k-1);
// reversing element range of k to last element.
reverse(arr, k, N-1);
cout << "Array after rotating by k-elements : ";
for(int i = 0;i<N;i++)
cout << arr[i] << " ";
return 0;
}輸出
Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
結論
在本文中，我們討論了使用反轉演算法將陣列向右旋轉 k 個元素的問題。我們討論了什麼是反轉演算法以及如何實現它來解決此問題。我們還討論了 C++ 程式碼來解決此問題。我們可以使用其他任何語言（如 C、Java、Python 等）編寫此程式碼。希望本文對您有所幫助。
更新於： 2021年11月29日
684 次檢視
廣告