Cでアレイを反転します
この投稿では、線形時間でCのアレイを反転する方法を説明します。
1.補助アレイの使用
簡単な解決策は、入力アレイと同じタイプとサイズの補助アレイを作成し、入力アレイの要素を逆方向に入力してから、補助アレイの内容を元のアレイにコピーすることです。このソリューションの時間計算量は O(n) とが必要です O(n) 余分なスペース、ここで n 入力のサイズです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <stdio.h> //アレイの内容を出力する関数 void print(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } //アレイの要素を反転する関数 void reverse(int arr[], int n) { int aux[n]; for (int i = 0; i < n; i++) { aux[n - 1 - i] = arr[i]; } for (int i = 0; i < n; i++) { arr[i] = aux[i]; } } int main(void) { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, n); print(arr, n); return 0; } |
2.インプレース実装
上記の実装には O(n) 補助アレイ用の余分なスペース。線形 インプレースアルゴリズム 以下に示すように、アレイの両端から要素を読み取り、それらを交換することで実装できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> //アレイの内容を出力する関数 void print(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } //アレイの要素を反転する関数 void reverse(int arr[], int n) { for (int low = 0, high = n - 1; low < high; low++, high--) { int temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } } int main(void) { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, n); print(arr, n); return 0; } |
3.再帰の使用
上記のコードを簡単に変換して、 再帰。ロジックは上記の反復実装と同じままですが、 O(n) の暗黙のスペース コールスタック.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <stdio.h> //アレイの内容を出力する関数 void print(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } //形成されたサブアレイの要素を反転する再帰的関数 // `arr[low, high]`によって void reverse(int arr[], int low, int high) { if (low < high) { int temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; reverse(arr, low + 1, high - 1); } } int main(void) { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, 0, n - 1); print(arr, n); return 0; } |
これは、要素をコールスタックに格納し、再帰的が展開されたときに正しい順序でアレイに戻す別の再帰的プログラムです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <stdio.h> //アレイの内容を出力する関数 void print(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } //アレイの要素を反転する関数 void reverse(int arr[], int i, int n) { //基本ケース：アレイの終わりに到達したか、アレイインデックスが範囲外です if (i >= n) { return; } //次のアレイ要素を格納します int value = arr[i]; //再帰を使用してアレイの最後に到達します reverse(arr, i + 1, n); //コールスタックの要素をアレイに戻します //正しい順序で arr[n - i - 1] = value; } int main(void) { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, 0, n); print(arr, n); return 0; } |
こちらも参照: