Algorithem_ReverseArray#
配列が与えられた場合、配列を右に k ステップ回転させます。ここで、k は非負です。
例 1：
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
右に1ステップ回転：[7,1,2,3,4,5,6]
右に2ステップ回転：[6,7,1,2,3,4,5]
右に3ステップ回転：[5,6,7,1,2,3,4]
例 2：
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
右に1ステップ回転：[99,-1,-100,3]
右に2ステップ回転：[3,99,-1,-100]
ReverseArray#
解法 1：
循環的に末尾の要素を取り出し、配列の最初の位置に挿入します。各取り出しのたびに k-1 を減らし、k=0 になるまで続けます。
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
// Solution 1
var times = k
while (times > 0) {
let last = nums.removeLast()
nums.insert(last, at: 0)
times -= 1
}
}
最終的な結果を得ることができますが、アルゴリズムには関係なく、reverseArrray はありません。
解法 2：
reverseArray のロジックは次のとおりです：nums=[1, 2, 3, 4, 5, 6, 7]、k = 3 の場合、[1, 2, 3, 4] を rotate して [4, 3, 2, 1] にし、[5, 6, 7] を rotate して [7, 6, 5] にし、それらを結合して [4, 3, 2, 1, 7, 6, 5] にし、さらに rotate して [5, 6, 7, 1, 2, 3, 4] にします。
コードは以下の通りです：
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
// Solution 2
let count = nums.count
let tempK = k % count
reverse(&nums, 0, count - tempK - 1)
reverse(&nums, count - tempK, count-1)
reverse(&nums, 0, count-1)
}
func reverse(_ nums: inout [Int], _ i: Int, _ j: Int) {
var mutI = i
var mutJ = j
while (mutI < mutJ) {
nums.swapAt(mutI, mutJ)
mutI += 1
mutJ -= 1
}
}
}