LeetCode題目如下：

首先這個(gè)中等難度我是沒(méi)搞懂，后面才發(fā)現(xiàn)原來(lái)中等中在要求多方法上，那就來(lái)看看怎么搞定他吧。

暴力思路

首先我說(shuō)一下我本人的思路，就是函數(shù)進(jìn)行倒序操作，分三步：

1.整體倒序 ：1234567-------7654321

2.前半部分倒序：7654321------- 5674321

3.后半部分倒序：5674321-------5671234

由于題目已經(jīng)給出了我們 k 的值，我們直接暴力思路（注意是暴力思路非暴力求解），雙指針交換對(duì)應(yīng)的值就行：

void exchange(int* a, int* b)
{
int n=*a;
*a = *b;
*b = n;
}   //交換a，b位置
void reverse(int* nums,int left,int right)
{
while(left<right)
{
exchange(&nums[left],&nums[right]);
left++;
right--;
}   //對(duì)指定范圍內(nèi)元素進(jìn)行翻轉(zhuǎn)操作
}
void rotate(int* nums, int numsSize, int k){
k%=numsSize;
if(k==0)
{
return ;  //防止k過(guò)大或0導(dǎo)致無(wú)意義操作
}
reverse(nums,0,numsSize-1);//全倒序
reverse(nums,0,k-1);//前半部分倒序
reverse(nums,k,numsSize-1);//后半部分倒序
}

這種方法直觀，最容易想到，特點(diǎn)是思路清晰，完美符合了流程，時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)，將將就就

外加數(shù)組

自力更生不想要咱就尋求外援嘛，直接創(chuàng)建一個(gè)額外數(shù)組，前半部分放前面，后半部分放后面不就行了，用 numsSize 表示數(shù)組的長(zhǎng)度，我們遍歷原數(shù)組，將原數(shù)組下標(biāo)為 n 的元素放至新數(shù)組下標(biāo)為 n+k 的位置，最后將新數(shù)組拷貝至原數(shù)組即可:

void rotate(int* nums, int numsSize, int k){
int arr[numsSize] = {0};
for(int n = 0;n<numsSize;n++)
{
arr[(k+n)%numsSize] = nums[n]; //nums所有元素向前移動(dòng) k 個(gè)單位，依次存到數(shù)組arr
}
for(int n = 0;n<numsSize;n++)
{
nums[n] = arr[n];  //將arr數(shù)組內(nèi)容拷貝回原數(shù)組nums
}

同理，我們可以選擇直接 malloc 一塊空間出來(lái)，這種方法同上不贅述

格局抬高

既然我們能想到 malloc 開(kāi)辟空間操作，那再想想庫(kù)函數(shù)里面好像還有個(gè)好東西叫 memcpy ，頭文件：#include <string.h>，memcpy() 用來(lái)復(fù)制內(nèi)存，且忽略 \0，其原型為：

  void * memcpy ( void * dest, const void * src, size_t num );

memcpy() 會(huì)復(fù)制 src 所指的內(nèi)存內(nèi)容的前 num 個(gè)字節(jié)到 dest 所指的內(nèi)存地址上。memcpy() 并不關(guān)心被復(fù)制的數(shù)據(jù)類型，只是逐字節(jié)地進(jìn)行復(fù)制，這給函數(shù)的使用帶來(lái)了很大的靈活性，可以面向任何數(shù)據(jù)類型進(jìn)行復(fù)制。

代碼如下：

void rotate(int* nums, int numsSize, int k){
int arr[numsSize];
k %= numsSize;
memcpy(arr,nums+(numsSize-k),k*(int)sizeof(int));
memcpy(arr+k,nums,(numsSize-k)*(int)sizeof(int));
memcpy(nums,arr,numsSize*(int)sizeof(int));
}

但是在重疊內(nèi)存塊這方面，memmove() 是比 memcpy() 更安全的方法，所以可能會(huì)有一個(gè)疑問(wèn)就是為什么不用 memmove？

memmove 相比 memcpy 更容易造成數(shù)據(jù)丟失。如果目標(biāo)區(qū)域和源區(qū)域有重疊的話，memmove() 能保證源串在被覆蓋之前將重疊區(qū)域的字節(jié)拷貝到目標(biāo)區(qū)域中，復(fù)制后源區(qū)域的內(nèi)容會(huì)被更改。如果目標(biāo)區(qū)域與源區(qū)域沒(méi)有重疊，則和 memcpy() 函數(shù)功能相同。

強(qiáng)調(diào)一下，與 strcpy() 不同的是，memcpy() 會(huì)完整的復(fù)制 num 個(gè)字節(jié)，不會(huì)因?yàn)橛龅?ldquo;\0”而結(jié)束。

環(huán)形替代

這是力扣上官方給出的一種方法，需要數(shù)學(xué)推導(dǎo)，比較難理解，解析給的是花里胡哨，添油加醋的，我大概概括一下就是把數(shù)組一串元素類比成莫比烏斯環(huán)，我們構(gòu)圖理解就簡(jiǎn)單多了(ppt手繪勿噴)：

什么意思呢，就是我們就拿k作為遍歷間隔，不斷拿 1+nk（n從0開(kāi)始） 位置的元素替代 1+ （n+1）k位置元素，直到回到原點(diǎn)，回到原點(diǎn)時(shí)因?yàn)楸闅v間隔>0，必定會(huì)有未遍歷的元素我們只需+1 跳到下一位置繼續(xù)上述操作，再使用另一單獨(dú)變量，跟蹤當(dāng)前已經(jīng)訪問(wèn)的元素?cái)?shù)量，當(dāng)該變量 = 元素?cái)?shù)量時(shí)遍歷完成，結(jié)束遍歷過(guò)程。（個(gè)人理解，如有不當(dāng)請(qǐng)聯(lián)系我更正喲~）

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);
    }
}

今天就到這里吧，摸了家人們，更多關(guān)于多方法超度旋轉(zhuǎn)數(shù)組的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論