您好,登錄后才能下訂單哦!
今天小編給大家分享一下C語言輪轉(zhuǎn)數(shù)組問題怎么解決的相關(guān)知識點,內(nèi)容詳細,邏輯清晰,相信大部分人都還太了解這方面的知識,所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
給你一個數(shù)組,將數(shù)組中的元素向右輪轉(zhuǎn) k 個位置,其中 k 是非負數(shù)。OJ鏈接
1.實例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.實例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]
為了使算法空間復(fù)雜度為O(1),原地旋轉(zhuǎn),所以不能額外創(chuàng)建數(shù)組。
以實例1為例子。使用三次逆轉(zhuǎn)法,讓數(shù)組旋轉(zhuǎn)k次
先整體逆轉(zhuǎn) 變?yōu)?code>(7,6,5,4,3,2,1)
逆轉(zhuǎn)子數(shù)組[0, k - 1] 變?yōu)?code>(5,6,7,4,3,2,1)
逆轉(zhuǎn)子數(shù)組[k, numsSize - 1] 變?yōu)?code>(5,6,7,1,2,3,4)
設(shè)置兩個指針變量分別指向頭部和尾部。當 begin<end 時,交換兩個位置上的值。綠色的數(shù)字為交換的位置。
此處不贅述、同上面兩個步驟的思路。這樣就完成了對數(shù)組的輪轉(zhuǎn)。
假如需要輪轉(zhuǎn)的個數(shù)k大于數(shù)組numsSize的長度呢?
假如k為10,那么本題的結(jié)果是什么呢?
假如右旋10個數(shù),那么先旋7個后將又回到了原來的樣子。 然后再旋3個的話那么將和本題的旋3個一模一樣。
本題的精髓就是題目,叫做輪轉(zhuǎn)數(shù)組。果然天道好輪回。輪轉(zhuǎn)7次又回到了起點。輪轉(zhuǎn)14次,21次…,只要七的倍數(shù)都回返回原地。
所以在題目中要加入是否為k的倍數(shù)的判斷代碼
if (k > numsSize) { k %= numsSize; }
此代碼帶主函數(shù)。LeetCode題目中是接口類型的不帶主函數(shù)。因為要輪轉(zhuǎn)三次。所以把while循環(huán)寫成一個函數(shù),方便復(fù)用。
LeetCode189. 輪轉(zhuǎn)數(shù)組 #include<stdio.h> void rotate1(int* begin, int* end) { while (begin < end) { int t = 0; t = *begin; *begin = *end; *end = t; ++begin; --end; } } void rotate(int* nums, int numsSize, int k) { //假如右旋10個數(shù),先旋7個后又回到了原來的樣子。然后再旋3次的話和本題再旋3次一模一樣。 if (k > numsSize) { k %= numsSize; } int* begin = nums; int* end = nums + numsSize - 1; rotate1(begin, end); rotate1(begin, begin+k-1); rotate1(begin + k, end); } int main() { int nums[] = { 1,2,3,4,5,6,7 }; int sz = sizeof(nums) / sizeof(nums[0]); rotate(nums, sz, 3); for (int i = 0; i < sz; i++) { printf("%d ", nums[i]); } return 0; }
以上就是“C語言輪轉(zhuǎn)數(shù)組問題怎么解決”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會為大家更新不同的知識,如果還想學習更多的知識,請關(guān)注億速云行業(yè)資訊頻道。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。