題目

題目鏈接：輪轉(zhuǎn)數(shù)組

給定一個(gè)整數(shù)數(shù)組 nums，將數(shù)組中的元素向右輪轉(zhuǎn) k 個(gè)位置，其中 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:

輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋: 
向右輪轉(zhuǎn) 1 步: [99,-1,-100,3]
向右輪轉(zhuǎn) 2 步: [3,99,-1,-100]

提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
進(jìn)階：
盡可能想出更多的解決方案，至少有 三種 不同的方法可以解決這個(gè)問題。
你可以使用空間復(fù)雜度為 O(1) 的 原地 算法解決這個(gè)問題嗎？

第一種解法：額外數(shù)組

代碼如下：

void rotate(int* nums, int numsSize, int k) {
    int newArr[numsSize];
    for (int i = 0; i < numsSize; ++i) {
        newArr[(i + k) % numsSize] = nums[i];
    }
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = newArr[i];
    }
}

復(fù)雜度分析：
時(shí)間復(fù)雜度： O(n)，其中 n 為數(shù)組的長(zhǎng)度。
空間復(fù)雜度： O(n)。
個(gè)人分析：
這種解法最妙的地方是（i+k)%numSize的運(yùn)用，值得多想想，這里是使用了一個(gè)變長(zhǎng)數(shù)組的寫法，使用了額外的數(shù)組空間接收反轉(zhuǎn)后的數(shù)組，再重新賦回原數(shù)組。
舉個(gè)例子：
nums[ ]={1,2,3,4,5},k=2,反轉(zhuǎn)后應(yīng)是nums[ ]={4,5,1,2,3};

初始條件：i=0  k=2  numsSize=5
第一趟   i=0   (i + k) % numsSize=2    newArr[2]=nums[0]
         newArr[]={ , ,1, , }
第二趟   i=1   (i + k) % numsSize=3    newArr[3]=nums[1]
         newArr[]={ , ,1,2, }
第三趟   i=2   (i + k) % numsSize=4    newArr[4]=nums[2]
         newArr[]={ , ,1,2,3}
第三趟   i=3   (i + k) % numsSize=0    newArr[0]=nums[3]
         newArr[]={4, ,1,2,3}
第四趟   i=4   (i + k) % numsSize=1    newArr[1]=nums[4]
         newArr[]={4,5,1,2,3}
i=numsSize 終止第一個(gè)循環(huán)

最后將利用for循環(huán)將newArr[ ]中的元素遍歷賦給nums數(shù)組即可。

第二種解法：環(huán)狀替換

代碼如下：

//最大公約數(shù)
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
//交換
void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    int count = gcd(k, numsSize);
    for (int start = 0; start < count; ++start) {
        int current = start;
        int prev = nums[start];
        do {
            int next = (current + k) % numsSize;
            swap(&nums[next], &prev);
            current = next;
        } while (start != current);
    }
}

復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n)，其中 n 為數(shù)組的長(zhǎng)度。每個(gè)元素只會(huì)被遍歷一次。
空間復(fù)雜度：O(1)。我們只需常數(shù)空間存放若干變量。
個(gè)人分析：
首先講講這里的gcd函數(shù)是一個(gè)求最大公約數(shù)的自定義函數(shù)，有很多小伙伴可能不理解這種寫法，可以替換成下面這種常規(guī)的輾轉(zhuǎn)相除寫法：

int gcd(int a, int b) {
    while(a%b)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    return b;
}

swap是常用的交換函數(shù)就不多講了，這種寫法的主要思路是將間隔為k的元素逐個(gè)向后替換，再將該間隔最后一個(gè)元素與開頭替換，求k與numsSize的最大公約數(shù)是為了將不同間隔數(shù)分組，設(shè)定循環(huán)次數(shù)，便于遍歷交換。
舉個(gè)例子：
nums[ ]={1,2,3,4,5,6},k=2,反轉(zhuǎn)后應(yīng)是nums[ ]={5,6,1,2,3,4};

初始條件：start=0  k=2  numsSize=6
第一趟 prev=nums[0]=1
       current=0  next=(current + k) % numsSize=2
       nums[2]=1  prev=3  nums[]={1,2,1,4,5,6}
       current=2  next=(current + k) % numsSize=4
       nums[4]=3  prev=5  nums[]={1,2,1,4,3,6}
       current=4  next=(current + k) % numsSize=0
       nums[0]=5  prev=1  nums[]={5,2,1,4,3,6}
       current=0=start  終止do...while循環(huán)
第二趟 prev=nums[1]=2
       current=1  next=(current + k) % numsSize=3
       nums[3]=2  prev=4  nums[]={5,2,1,2,3,6}
       current=3  next=(current + k) % numsSize=5
       nums[5]=4  prev=6  nums[]={5,2,1,2,3,4}
       current=5  next=(current + k) % numsSize=1
       nums[1]=6  prev=2  nums[]={5,6,1,2,3,4}
       current=1=start  終止do...while循環(huán)
start=2=count  終止for循環(huán)

提一下這里的k=k%numsSize操作，我覺得是個(gè)優(yōu)化吧，假設(shè)這里k=8，實(shí)際和k=2的最終結(jié)果是一樣的，這樣可以做性能上的優(yōu)化吧，然后就是這里count是用于循環(huán)條件的，也可以不使用最大公約數(shù)的賦值寫法，也可以在while循環(huán)里加一個(gè)變量記錄被訪問的元素，當(dāng)count等于這個(gè)值時(shí)，結(jié)束遍歷也可。

第三種解法：翻轉(zhuǎn)數(shù)組

代碼如下：

//交換
void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}
//數(shù)組反轉(zhuǎn)
void reverse(int* nums, int start, int end) {
    while (start < end) {
        swap(&nums[start], &nums[end]);
        start++;
        end++;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;
    reverse(nums, 0, numsSize - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, numsSize - 1);
}

復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n)，其中 n 為數(shù)組的長(zhǎng)度。每個(gè)元素被翻轉(zhuǎn)兩次，一共 n 個(gè)元素，因此總時(shí)間復(fù)雜度為 O(2n)=O(n)。
空間復(fù)雜度：O(1)。
個(gè)人分析：
這個(gè)算法的思路是先將整個(gè)數(shù)組先反轉(zhuǎn)，再將前后兩部分分別反轉(zhuǎn)，個(gè)人認(rèn)為比前兩種寫法更好理解一些。這里的反轉(zhuǎn)的寫法是采用前后指針的交換寫法。同樣的，舉個(gè)例子：
nums[ ]={1,2,3,4,5},k=2,反轉(zhuǎn)后應(yīng)是nums[ ]={4,5,1,2,3};

初始條件：  k=2  numsSize=5
第一趟      nums[]={5,4,3,2,1}
第二趟      nums[]={4,5,3,2,1}
第三趟      nums[]={4,5,1,2,3}

結(jié)語(yǔ)

這里的解法代碼來(lái)自力扣官方，作者只是進(jìn)行了詳細(xì)的剖析和部分改動(dòng)
方便大家理解和提升自己，學(xué)會(huì)多角度觀察問題，解決問題。

有興趣的小伙伴可以關(guān)注作者，如果覺得內(nèi)容不錯(cuò)，請(qǐng)給個(gè)一鍵三連吧，蟹蟹你喲?。?！
制作不易，如有不正之處敬請(qǐng)指出
感謝大家的來(lái)訪，UU們的觀看是我堅(jiān)持下去的動(dòng)力
在時(shí)間的催化劑下，讓我們彼此都成為更優(yōu)秀的人吧！??！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-446589.html

到了這里，關(guān)于（C語(yǔ)言版）力扣（LeetCode）189. 輪轉(zhuǎn)數(shù)組官方3種解法分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！