程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 189 Rotate Array(旋轉數組)

LeetCode 189 Rotate Array(旋轉數組)

編輯:C++入門知識

LeetCode 189 Rotate Array(旋轉數組)


翻譯

通過K步將一個有著n個元素的數組旋轉到右側。

例如,
給定n = 7和k = 3,數組[1,2,3,4,5,6,7]會被旋轉成[5,6,7,1,2,3,4]。

批注:
盡你可能嘗試多種解決方案,這裡至少存在3種不同的方式去解決這個問題。

原文

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

分析

第一種方法

我所想到的第一種方式是另設置一個vector,然後逐個元素添加進去,最後將這個vector賦值給nums。添加方式為將右邊的k個元素添加進去,再將左邊的n-k個元素添加進去。

具體代碼為:

void rotate(vector &nums, int k) {
    if (nums.size() == 1) return;
    if (k > nums.size())  k %= nums.size();
    vector newNums;
    for (int i = nums.size() - k; i < nums.size(); ++i)
        newNums.push_back(nums[i]);
    for (int i = 0; i < nums.size() - k; ++i)
        newNums.push_back(nums[i]);
    nums = newNums;
}

Runtime: 28 ms

超時方法

還有一個最簡單的方法,不過妥妥的超時了……

void rotate(vector &nums, int k) {
    if (nums.size() <= 1) return;
    if (k > nums.size()) k %= nums.size();
    while (k > 0) {
        int temp = nums[nums.size() - 1];
        for (int i = nums.size() -1; i >0; --i) {
            nums[i] = nums[i - 1];
        }
        nums[0] = temp;
        k--;
    }
}

Time Limit Exceeded

第二種方法

上面那種方法不行,繼續改進第一種方法。同樣是將vector切成左右兩邊。

void rotate(vector &nums, int k) {
    if (nums.size() <= 1) return;
    if (k > nums.size()) k %= nums.size();
    vector extra(nums.begin(), nums.begin() + nums.size() - k);
    nums.erase(nums.begin(), nums.begin() + nums.size() - k);
    nums.insert(nums.end(), extra.begin(), extra.end());
}

Runtime: 28 ms

第二種方法改進

試試顛倒順序呢?

void rotate(vector &nums, int k) {
    if (nums.size() <= 1) return;
    if (k > nums.size()) k %= nums.size();
    vector extra(nums.end() - k, nums.end());
    nums.erase(nums.end() - k, nums.end());
    nums.insert(nums.begin(), extra.begin(), extra.end());
}

Runtime: 24 ms

要少了4秒呢。

第三種方法

還有一種方法,可以使用STL自帶的rotate()函數……

void rotate(vector& nums, int k) {
    int len = nums.size();
    if (len > 1) {
        k %= len;
        std::rotate(nums.begin(), nums.end() - k, nums.end());
    }
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved