柚子快報邀請碼778899分享：【初階數(shù)據(jù)結(jié)構(gòu)】復雜度算法題篇

http://yzkb.51969.com/

旋轉(zhuǎn)數(shù)組

力扣原題

方案一

循環(huán)K次將數(shù)組所有元素向后移動?位（代碼不通過)

時間復雜度O(n2) 空間復雜度O(1)

void rotate(int* nums, int numsSize, int k) {

while (k--) {

int end = nums[numsSize - 1];

for (int i = numsSize - 1; i > 0; i--) {

nums[i] = nums[i - 1];

}

nums[0] = end;

}

}

時間復雜度過高，需要優(yōu)化

方案二

申請新數(shù)組空間，先將后k個數(shù)據(jù)放到新數(shù)組中，再將剩下的數(shù)據(jù)挪到新數(shù)組中

時間復雜度O(n) 空間復雜度O(n)

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];

}

}

記得最后要把新數(shù)組數(shù)據(jù)復制到原數(shù)組時間復雜度降低了，可以通過空間復雜度提升，仍可以優(yōu)化

方案三

數(shù)組翻轉(zhuǎn)

該方法基于如下的事實：當我們將數(shù)組的元素向右移動 k 次后，尾部 kmodn 個元素會移動至數(shù)組頭部，其余元素向后移動 kmodn 個位置。

我們可以先將所有元素翻轉(zhuǎn)，這樣尾部的 kmodn 個元素就被移至數(shù)組頭部，然后我們再翻轉(zhuǎn) [0,kmodn?1] 區(qū)間的元素和 [kmodn,n?1] 區(qū)間的元素即能得到最后的答案

時間復雜度：O(n) 空間復雜度：O(1)

void reverse(int* nums, int begin, int end) {

while (begin < end) {

int tmp = nums[begin];

nums[begin] = nums[end];

nums[end] = tmp;

begin++;

end--;

}

}

void rotate(int* nums, int numsSize, int k) {

k = k % numsSize;

reverse(nums, 0, numsSize - k - 1);

reverse(nums, numsSize - k, numsSize - 1);

reverse(nums, 0, numsSize - 1);

}

柚子快報邀請碼778899分享：【初階數(shù)據(jù)結(jié)構(gòu)】復雜度算法題篇

http://yzkb.51969.com/

好文推薦