C語言雙指針多方法旋轉數組解題LeetCode
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其它相關文章!