C語言雙指針多方法旋轉數組解題LeetCode

Posted on by

LeetCode題目如下：

在這裡插入圖片描述

首先這個中等難度我是沒搞懂，後面才發現原來中等中在要求多方法上，那就來看看怎麼搞定他吧。

暴力思路

首先我說一下我本人的思路，就是函數進行倒序操作，分三步：

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

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

3.後半部分倒序：5674321——-5671234

由於題目已經給出瞭我們 k 的值，我們直接暴力思路（註意是暴力思路非暴力求解），雙指針交換對應的值就行：

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--;
}   //對指定范圍內元素進行翻轉操作
}
void rotate(int* nums, int numsSize, int k){
k%=numsSize;
if(k==0)
{
return ;  //防止k過大或0導致無意義操作
}
reverse(nums,0,numsSize-1);//全倒序
reverse(nums,0,k-1);//前半部分倒序
reverse(nums,k,numsSize-1);//後半部分倒序
}

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

外加數組

自力更生不想要咱就尋求外援嘛，直接創建一個額外數組，前半部分放前面，後半部分放後面不就行瞭，用 numsSize 表示數組的長度，我們遍歷原數組，將原數組下標為 n 的元素放至新數組下標為 n+k 的位置，最後將新數組拷貝至原數組即可:

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所有元素向前移動 k 個單位，依次存到數組arr
}
for(int n = 0;n<numsSize;n++)
{
nums[n] = arr[n];  //將arr數組內容拷貝回原數組nums
}

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

格局抬高

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

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

memcpy() 會復制 src 所指的內存內容的前 num 個字節到 dest 所指的內存地址上。memcpy() 並不關心被復制的數據類型，隻是逐字節地進行復制，這給函數的使用帶來瞭很大的靈活性，可以面向任何數據類型進行復制。

代碼如下：

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

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

memmove 相比 memcpy 更容易造成數據丟失。如果目標區域和源區域有重疊的話，memmove() 能保證源串在被覆蓋之前將重疊區域的字節拷貝到目標區域中，復制後源區域的內容會被更改。如果目標區域與源區域沒有重疊，則和 memcpy() 函數功能相同。

強調一下，與 strcpy() 不同的是，memcpy() 會完整的復制 num 個字節，不會因為遇到“\0”而結束。

環形替代

在這裡插入圖片描述

這是力扣上官方給出的一種方法，需要數學推導，比較難理解，解析給的是花裡胡哨，添油加醋的，我大概概括一下就是把數組一串元素類比成莫比烏斯環，我們構圖理解就簡單多瞭(ppt手繪勿噴)：

在這裡插入圖片描述

什麼意思呢，就是我們就拿k作為遍歷間隔，不斷拿 1+nk（n從0開始） 位置的元素替代 1+ （n+1）k位置元素，直到回到原點，回到原點時因為遍歷間隔>0，必定會有未遍歷的元素我們隻需+1 跳到下一位置繼續上述操作，再使用另一單獨變量，跟蹤當前已經訪問的元素數量，當該變量 = 元素數量時遍歷完成，結束遍歷過程。（個人理解，如有不當請聯系我更正喲~）

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

今天就到這裡吧，摸瞭傢人們，更多關於多方法超度旋轉數組的資料請關註WalkonNet其它相關文章！

推薦閱讀：