這題目我以前在臉書就看過了,也還不知道如何解釋
題意,給一整數陣列,陣列長度n,以及一整數k,將陣列向右移動k次,往右邊移動的那一位填補到最左邊的空位
例如
[1,2,3],1 ->[3,1,2]
[1,2,3,4,5,6,7],2 -> [6,7,1,2,3,4,5]
操作方法是先將全部reverse,再reverse前面第零個到第k個,最後reverse第k個後面到結尾
考慮進去三次reverse,時間複雜度為O(2n)
class Solution { public: void rotate(int nums[], int n, int k) { reverse(nums, nums+n); reverse(nums, nums+k%n); reverse(nums+k%n, nums+n); } };
想出解釋的方法了
向右移動 k 次,代表會有末尾 k 位跑到右邊去
所以先將整個數列反轉一次之後,把前面 k 位再反轉一次,就可以讓前面 k 位保持原本的順序
然後在將後面 n-k 位翻轉一次,讓後面剩下的位數也都保持原本的順序
這樣就完成了