【力扣】189. 輪轉數組

1. 題目介紹

給定一個整數數組 nums，將數組中的元素向右輪轉 k 個位置，其中 k 是非負數。

2. 解法

2.1 方法一：不太正規，但是簡單

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 方法二：使用額外的數組

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

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 方法三：環狀替換

• 需要了解一個定理，環的個數等于：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 方法四：數組翻轉

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）是領扣網絡旗下專注于程序員技術成長和企業技術人才服務的品牌。源自美國硅谷，力扣為全球程序員提供了專業的IT技術職業化提升平臺，有效幫助程序員實現快速進步和長期成長。此外，力扣（LeetCode）致力于解決程序員技術評估、培訓、職業匹配的痛點，逐步引領互聯網技術求職和招聘邁向專業化。

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

參考

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