【力扣】189. 輪轉(zhuǎn)數(shù)組

1. 題目介紹

給定一個整數(shù)數(shù)組 nums，將數(shù)組中的元素向右輪轉(zhuǎn) k 個位置，其中 k 是非負(fù)數(shù)。

2. 解法

2.1 方法一：不太正規(guī)，但是簡單

class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""k = k % len(nums)for i in range(k):tem = nums.pop()nums.insert(0, tem)return nums

2.2 方法二：使用額外的數(shù)組

• 我們可以使用額外的數(shù)組來將每個元素放至正確的位置。用 n 表示數(shù)組的長度，我們遍歷原數(shù)組，將原數(shù)組下標(biāo)為 i 的元素放至新數(shù)組下標(biāo)為(i+k) mod n 的位置，最后將新數(shù)組拷貝至原數(shù)組即可。

class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();vector<int> newArr(n);for (int i = 0; i < n; ++i) {newArr[(i + k) % n] = nums[i];}nums.assign(newArr.begin(), newArr.end());}
};

2.3 方法三：環(huán)狀替換

• 需要了解一個定理，環(huán)的個數(shù)等于：gcd(k, n)
  

class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k = k % n;int count = gcd(k, n);for (int start = 0; start < count; ++start) {int current = start;int prev = nums[start];do {int next = (current + k) % n;swap(nums[next], prev);current = next;} while (start != current);}}
};

2.4 方法四：數(shù)組翻轉(zhuǎn)

class Solution {
public:void reverse(vector<int>& nums, int start, int end) {while (start < end) {swap(nums[start], nums[end]);start += 1;end -= 1;}}void rotate(vector<int>& nums, int k) {k %= nums.size();reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};

3. Danger

力扣（LeetCode）是領(lǐng)扣網(wǎng)絡(luò)旗下專注于程序員技術(shù)成長和企業(yè)技術(shù)人才服務(wù)的品牌。源自美國硅谷，力扣為全球程序員提供了專業(yè)的IT技術(shù)職業(yè)化提升平臺，有效幫助程序員實(shí)現(xiàn)快速進(jìn)步和長期成長。此外，力扣（LeetCode）致力于解決程序員技術(shù)評估、培訓(xùn)、職業(yè)匹配的痛點(diǎn)，逐步引領(lǐng)互聯(lián)網(wǎng)技術(shù)求職和招聘邁向?qū)I(yè)化。

• 據(jù)了解到的情況，Easy題和Medium 題在面試中比較常見，通常會以手寫代碼之類的形式出現(xiàn)，您需要對問題進(jìn)行分析并給出解答，并于面試官進(jìn)行交流溝通，有時還會被要求分析時間復(fù)雜度8與空間復(fù)雜度°，面試官會通過您對題目的分析解答，了解您對常用算法的熟悉程度和您的程序?qū)崿F(xiàn)功底。
• 而在一些對算法和程序?qū)崿F(xiàn)功底要求較高的崗位，Hard 題也是很受到面試官的青睞，如果您在面試中成功Bug-Free出一道Hard題，我們相信您一定會給面試官留下很深刻的印象，并極大增加拿到Offer的概率，據(jù)相關(guān)人士統(tǒng)計(jì)，如果您在面試成功解出一道Hard題，拿不到Offer的概率無限接近于0。
• 所以,力扣中Easy和Medium相當(dāng)于面試中的常規(guī)題，而Hard 則相當(dāng)于面試中較難的題，解出—道Hard題，Offer可以說是囊中之物。

參考

【1】鏈接：https://leetcode.cn/problems/rotate-array/ 來源：力扣（LeetCode）