思路一：
由該題的解題示例可以想到的最簡單的一種思路
將陣列最后一個元素取出，把剩余元素依次向右移動，最后將取出的最后一個元素放到陣列的首位，要進行多少多少次陣列旋轉，就進行多少次操作
void rotate(int* nums, int numsSize, int k){
int temp=0;
int i=0;
int m=k%numsSize;
for(i=0;i<=m,i++)
{
temp=nums[numsSize-1];
for(int j=numsSize-2;j>0;--j)
{
nums[j+1]=nums[j];
}
nums[0]=temp;
}
}
此思路中時間復雜度為O(N*K),空間復雜度為O(1)
思路二：
對于時間有要求的題目，可以考慮以時間換取空間的思路，即開辟一塊新的空間來降低時間復雜度
若是要求進行k次陣列旋轉操作，也就意味著將陣列的后k位和陣列的前numsSize-k位進行位置調換，因此另外建立一個陣列，將后k位依次拷貝到新建的陣列中，然后將原陣列中剩下的元素依次拷貝到新陣列中
void rotate(int* nums, int numsSize, int k){
int* ret = (int*)malloc(sizeof(int)*numsSize);
memset(ret, 0, sizeof(int)*numsSize);//開辟一個新陣列
int i = 0;
int j = k%numsSize;//對旋轉次數取余
if (numsSize>1&&j!=0)//判斷元素個數是否為一，若是一則不必處理
{
for (i = 0; i<j; i++)
{
ret[i] = nums[numsSize - j + i];//將nums陣列中最后k個元素拷貝到ret陣列中
}
for (i = 0; i<numsSize - j; i++)
{
ret[j + i] = nums[i];//把nums陣列中前面的元素拷貝到ret陣列中
}
for (i = 0; i<numsSize; i++)
{
nums[i] = ret[i];//將ret陣列拷貝回原陣列
}
}
}
注意點：
（1）當k=numsSize時，相當于原陣列沒有進行任何變化，當k>numsSize時，相當于進行了k%numsSize次陣列旋轉，所以一定要考慮到次數的邊界問題
（2）要考慮到特殊情況：當陣列的元素為一個或者numsSize=k時，輸出的陣列是和原陣列完全相同的，因此在這里要做一個判斷，若是滿足條件，則不必再進行旋轉操作
（3）在函式中若是開辟了新陣列的一定要將新陣列中的資料拷貝到原陣列中
該死了時間復雜度為O（N），因為開辟了相同大小的陣列，所以空間復雜度為O（N）
思路三：
若是進行k次陣列旋轉，將陣列最后k個元素依次逆序，陣列剩下的元素依次逆序，再把整個陣列中的元素依次逆序
void reserve(int* nums,int left,int right)
{
while(left<right)
{
int temp;
temp=nums[left];
nums[left]=nums[right];
nums[right]=temp;
++left;
--right;
}//定義逆序函式
}
void rotate(int* nums, int numsSize, int k){
int j=k%numsSize;
reserve(nums,0,numsSize-j-1);//對陣列前numsSize-k個元素進行逆序
reserve(nums,numsSize-j,numsSize-1);//對最后k個元素逆序
reserve(nums,0,numsSize-1);//整個陣列逆序
}
該思路時間復雜度為O（N），空間復雜度為O（1）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/274421.html
標籤：其他