旋轉陣列問題
題目描述
給定一個陣列，將陣列中的元素向右移動 k 個位置，其中 k 是非負數，
方法一：
分析：
一個陣列【1，2，3，4，5，6，7】如果旋轉3次，得到的陣列就是【5，6，7，1，2，3，4】，方法一是最好想的方法，我們一次一次旋轉陣列，每次都把陣列中最后一個元素放到第一個位置，把剩余的元素都向后挪動一個位置，重復k次操作，就得到了結果，
代碼實作
void change(int* arr, int size) //每次旋轉一次
{
int tmp = arr[size - 1]; //保存最后一個元素
int i = 0;
for (i = size-2; i >= 0; i--) //將剩余元素全部向挪動一位
{
arr[i + 1] = arr[i];
}
arr[0] = tmp; //將原來最后位置的數放到第一位
}
void change_sort(int*arr, int size, int k) //arr-陣列 size-陣列元素個數 k-旋轉次數
{
for (int i = 0; i < k; i++) //旋轉k次
{
change(arr, size);
}
}
劣勢：
這種方法的時間復雜度為O（k*n）所以說是不高效的
方法二：
分析：
我們可以重新開辟一塊空間，將原陣列的資料按照旋轉之后的移動下來，再把資料拷貝回去
代碼實作
int main()
{
int k = 3;
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int sz = sizeof(arr) / sizeof(arr[0]); //sz-陣列元素個數
int* a = (int*)malloc(sz*sizeof(int)); //新開辟一塊空間
int i = 0;
for (i = 0; i < sz - k; i++) //將arr中前sz-k個元素放在a的后面
{
a[k + i] = arr[i]; //arr->0~k-sz-1 //a->k~sz-1 (下標)
}
for (i = 0; i < k; i++) //將arr中后k個元素放在a的前面
{
a[i] = arr[sz-k+i]; //arr->sz-k~sz-1 //a->0~k-1 (下標)
}
for (i = 0; i < sz; i++)
arr[i] = a[i]; //最后將陣列拷貝回去
return 0;
}
劣勢：
需要重新開辟一塊空間，空間復雜度為O(N)
方法三：
分析：
將陣列分為前n-k個和后n個，分別將該兩部分逆置，再將整個陣列逆置，即可得到最后結果，
代碼實作：
void reverse(int*arr, int left, int right)
{
while (left < right) //不斷交換頭尾兩端資料
{
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
}
}
int main()
{
int k = 3;
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int sz = sizeof(arr) / sizeof(arr[0]); //求元素個數
reverse(arr,0,sz-k-1); //逆置前sz-k個資料
reverse(arr,sz-k,sz-1); //逆置后k個資料
reverse(arr,0,sz-1); //整體逆置
return 0;
}
優勢：
時間復雜度為O（N），空間復雜度為O（1）所以比上面兩種方法都高效
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/274437.html
標籤：其他
上一篇：論文《Variational quantum state diagonalization》閱讀筆記2（cost function構造！！！）