題目

1.題目描述

給你一個數(shù)組，將數(shù)組中的元素向右輪轉(zhuǎn) k?個位置，其中?k?是非負(fù)數(shù)。

示例 1:

輸入:

nums = [1,2,3,4,5,6,7], k = 3

輸出:

[5,6,7,1,2,3,4]?

解釋:

向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]

向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]

向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

2.要求

進(jìn)階：

• 盡可能想出更多的解決方案，至少有?三種?不同的方法可以解決這個問題。
• 你可以使用空間復(fù)雜度為?O(1)?的?原地?算法解決這個問題嗎？

3.原題鏈接

?189. 輪轉(zhuǎn)數(shù)組 - 力扣（LeetCode） (leetcode-cn.com)

二、相關(guān)知識點

本題實際上涉及到了復(fù)雜度的問題，包括時間復(fù)雜度和空間復(fù)雜度。

三、解決思路

旋轉(zhuǎn)法

最優(yōu)思路，這需要我們有較好的理解力了，可以把數(shù)組分為三個部分

假設(shè)我們需要選擇k個數(shù)字：

1.后k個數(shù)字逆置

2.前n-k個數(shù)字逆置

3.整體逆置

此方法為最優(yōu)法。符合題目要求

以示例 1為例子說明：

1 2 3 4 5 6 7//旋轉(zhuǎn)3個數(shù)字
1 2 3 4 7 6 5//后k個數(shù)字逆置
4 3 2 1 7 6 5//前n-k個數(shù)字逆置
5 6 7 1 2 3 4//整體逆置

源代碼如下：

void reverse(int*nums,int left,int right)
{
    while(left<right)
    {
        int tmp = nums[left];
        nums[left]=nums[right];
        nums[right] = tmp;
        ++left;
        --right;
    }
}
void rotate(int* nums, int numsSize, int k){
    k%=numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

注意點：k的大小可能大于數(shù)組的大小，所以我們要取模！

這個算法的時間復(fù)雜度為O（N），空間復(fù)雜度為O（1）

附上結(jié)果運行圖：

直接法

看到這道題，我們的第一種想法就是直接去旋轉(zhuǎn)，當(dāng)k=1是。我們就直接把最后一位的數(shù)字移動第一位，然后第二位開始往后移動，我們可以創(chuàng)建一個臨時的變量來記錄當(dāng)前的最后一位，當(dāng)k很大時，我們自然就是用循環(huán)去做，這是每個人都能想得到的一種方法

代碼如下

void rotate(int* nums, int numsSize, int k){
    k %=numsSize;
  while(k--){
      int tmp = nums[numsSize-1];
      for(int end = numsSize-2;end>=0;--end){
          nums[end+1] = nums[end];
      }
      nums[0] = tmp;
  }
}

遺憾的是，這種算法的空間復(fù)雜（k*N），沒能跑得過去，超時了，給出運行結(jié)果圖

空間換取時間

以空間換取時間，這是比較常見的，就是額外開辟一個數(shù)組，存放選擇的幾個數(shù)字，然后將之前的數(shù)據(jù)存儲到該數(shù)組的后半部分。最后將新數(shù)組拷貝到原來的數(shù)組中

代碼如下

void rotate(int* nums, int numsSize, int k){
   k %= numsSize;
   int *newnum = (int*)malloc(sizeof(int)*numsSize);
   int j = 0;
   for(int i =numsSize-k;i<numsSize;i++){
       newnum[j++] =nums[i];
   }
   for(int i = 0;i<numsSize-k;i++){
       newnum[i+k] = nums[i];
   }
   memcpy(nums,newnum,sizeof(int)*numsSize);
}

運行結(jié)果如圖

雖然也是通過了，但是效率不如思路一。