⓹➆ Rotate Array

Top Interview 150, Leetcode medium, C++, Algorithm

今日題目

Solution 1

有想法但是：

Time Limit Exceeded

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int length = nums.size();
        if(k == 0 || k % length == 0 ){
            return;
        }else{
            int move_round = k % length;
            //移動後面一點點
            if(move_round < length / 2){
                for(int i = 0; i < move_round; i++){
                    int temp = nums[length - 1];
                    for(int j = length - 1; j > 0; j--){
                        nums[j] = nums[j - 1];
                    }
                    nums[0] = temp;
                }
            }else{
                int left_move_round = length - move_round;
                for(int i = 0; i < left_move_round; i++){
                    int temp = nums[0];
                    for(int j = 0; j < length - 1; j++){
                        nums[j] = nums[j + 1];
                    }
                    nums[length - 1] = temp;
                }
            }
        }
    }
};

Solution 2

這裡的做法是新創一個temp vector去儲存我們整理後的順序分成三次，去做賦值。其實滿簡單的，此外時間複雜度為O(n)。

submit後也是成功執行，不過執行時間算是偏慢的。可能是因為我們真的Traverse整個vector

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int length = nums.size();
        if(k == 0 || k % length == 0 ){
            return;
        }else{
            int move_round = k % length;
            vector<int> temp(length);
            for(int i = 0, j = length - move_round; i < move_round; i++, j++){
                temp[i] = nums[j];
            }
            for(int i = move_round, j = 0; i < length; i++, j++){
                temp[i] = nums[j];
            }
            for(int i = 0; i < length; i++){
                nums[i] = temp[i];
            } 
            
        }
    }
};

Solution 3

我們可以動手試一試，假設一個陣列[1, 2, 3, 4, 5, 6, 7]，假設當k = 3時，此時我們可以將元陣列分成兩個部分。

k = 3; // 後半段三個元素會被移動變成>>>[5, 6, 7, 1, 2, 3, 4]
// 依上述所說，原列我們分成兩部分
[1, 2, 3, 4,\\ 5, 6, 7]
    part 1   \\ part 2
------------------------------
//接著，我們個別把part 1, part 2 reverse
//reverse part1
[4, 3, 2, 1, \\ 5, 6, 7]
reversed part1\\ part 2
------------------------------
// reverse part 2
[4, 3, 2, 1, \\ 7, 6, 5]
reversed part1\\reversed part2 
------------------------------
// 最後我們將整個陣列reverse過來
[5, 6, 7, 1, 2, 3, 4]
// 巧妙地符合題目需求。

有了想法後，接著就是把想法變成可以操作的程式碼。

class Solution {
public:
// 自定義function用於翻轉vector
    void reverse(vector<int>& nums1, int left_index, int right_index){
        while(left_index < right_index){
            int temp = nums1[left_index];
            nums1[left_index] = nums1[right_index];
            nums1[right_index] = temp;
            left_index++;
            right_index--;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int length = nums.size();
        if(k == 0 || k % length == 0){
            return;
        }else{
            int move_round = k % length;

            // if(k < 0){
            //     move_round = k + length;
            // }
            // reverse first part elements

            reverse(nums, 0, length - move_round - 1);
            reverse(nums, length - move_round, length - 1);
            reverse(nums, 0, length - 1);
        }
    }
};

https://leetcode.com/problems/rotate-array/submissions/1276130710?envType=study-plan-v2&envId=top-interview-150