91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

C++如何實現旋轉數組

發布時間:2022-03-28 10:57:08 來源:億速云 閱讀:234 作者:iii 欄目:大數據

這篇文章主要講解了“C++如何實現旋轉數組”,文中的講解內容簡單清晰,易于學習與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學習“C++如何實現旋轉數組”吧!

Rotate Array 旋轉數組

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input:

[1,2,3,4,5,6,7]

and k = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right:

[7,1,2,3,4,5,6]

rotate 2 steps to the right:

[6,7,1,2,3,4,5]

rotate 3 steps to the right:

[5,6,7,1,2,3,4]

Example 2:

Input:

[-1,-100,3,99]

and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

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

  • Could you do it in-place with O(1) extra space? 

新題搶先刷,這道題標為 Easy,應該不是很難,我們先來看一種 O(n) 的空間復雜度的方法,我們復制一個和 nums 一樣的數組,然后利用映射關系 i -> (i+k)%n 來交換數字。代碼如下:

解法一:

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

由于提示中要求我們空間復雜度為 O(1),所以我們不能用輔助數組,上面的思想還是可以使用的,但是寫法就復雜的多,而且需要用到很多的輔助變量,我們還是要將 nums[idx] 上的數字移動到 nums[(idx+k) % n] 上去,為了防止數據覆蓋丟失,我們需要用額外的變量來保存,這里用了 pre 和 cur,其中 cur 初始化為了數組的第一個數字,然后當然需要變量 idx 標明當前在交換的位置,還需要一個變量 start,這個是為了防止陷入死循環的,初始化為0,一旦當 idx 變到了 strat 的位置,則 start 自增1,再賦值給 idx,這樣 idx 的位置也改變了,可以繼續進行交換了。舉個例子,假如 [1, 2, 3, 4], K=2 的話,那么 idx=0,下一次變為 idx = (idx+k) % n = 2,再下一次又變成了 idx = (idx+k) % n = 0,此時明顯 1 和 3 的位置還沒有處理過,所以當我們發現 idx 和 start 相等,則二者均自增1,那么此時 idx=1,下一次變為 idx = (idx+k) % n = 3,就可以交換完所有的數字了。

因為長度為n的數組只需要更新n次,所以我們用一個 for 循環來處理n次。首先 pre 更新為 cur,然后計算新的 idx 的位置,然后將 nums[idx] 上的值先存到 cur 上,然后把 pre 賦值給 nums[idx],這相當于把上一輪的 nums[idx] 賦給了新的一輪,完成了數字的交換,然后 if 語句判斷是否會變到處理過的數字,參見上面一段的解釋,我們用題目中的例子1來展示下面這種算法的 nums 的變化過程:

1 2 3 4 5 6 7
1 2 3 1 5 6 7
1 2 3 1 5 6 4
1 2 7 1 5 6 4
1 2 7 1 5 3 4
1 6 7 1 5 3 4
1 6 7 1 2 3 4
5 6 7 1 2 3 4

解法二:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int start = 0, idx = 0, pre = 0, cur = nums[0], n = nums.size();
        for (int i = 0; i < n; ++i) {
            pre = cur;
            idx = (idx + k) % n;
            cur = nums[idx];
            nums[idx] = pre;
            if (idx == start) {
                idx = ++start;
                cur = nums[idx];
            }
        }
    }
};

這道題其實還有種類似翻轉字符的方法,思路是先把前 n-k 個數字翻轉一下,再把后k個數字翻轉一下,最后再把整個數組翻轉一下:

1 2 3 4 5 6 7
4 3 2 1 5 6 7
4 3 2 1 7 6 5
5 6 7 1 2 3 4

解法三:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int n = nums.size();
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

由于旋轉數組的操作也可以看做從數組的末尾取k個數組放入數組的開頭,所以我們用 STL 的 push_back 和 erase 可以很容易的實現這些操作。

解法四:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int n = nums.size();
        for (int i = 0; i < n - k; ++i) {
            nums.push_back(nums[0]);
            nums.erase(nums.begin());
        }
    }
};

下面這種方法其實還蠻獨特的,通過不停的交換某兩個數字的位置來實現旋轉,根據網上這個帖子的思路改寫而來,數組改變過程如下:

1 2 3 4 5 6 7
5 2 3 4 1 6 7
5 6 3 4 1 2 7
5 6 7 4 1 2 3
5 6 7 1 4 2 3
5 6 7 1 2 4 3
5 6 7 1 2 3 4

解法五:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty()) return;
        int n = nums.size(), start = 0;   
        while (n && (k %= n)) {
            for (int i = 0; i < k; ++i) {
                swap(nums[i + start], nums[n - k + i + start]);
            }
            n -= k;
            start += k;
        }
    }
};

感謝各位的閱讀,以上就是“C++如何實現旋轉數組”的內容了,經過本文的學習后,相信大家對C++如何實現旋轉數組這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是億速云,小編將為大家推送更多相關知識點的文章,歡迎關注!

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

c++
AI

商河县| 满城县| 治县。| 新昌县| 屏南县| 东城区| 和田县| 宜宾县| 拜泉县| 临桂县| 宕昌县| 潼南县| 岑溪市| 华宁县| 苗栗县| 赤壁市| 宣恩县| 中方县| 勐海县| 宝应县| 邢台市| 平定县| 紫云| 玛纳斯县| 斗六市| 基隆市| 东安县| 定远县| 正蓝旗| 南岸区| 九江县| 香河县| 西林县| 嘉荫县| 洪雅县| 宜兰市| 霍州市| 许昌市| 积石山| 毕节市| 曲麻莱县|