アルゴリズム_逆配列

Algorithem_ReverseArray#

与えられた配列を、k ステップ右に回転させます。k は非負です。

例 1:


入力: nums = [1,2,3,4,5,6,7], k = 3
出力: [5,6,7,1,2,3,4]
説明:
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:


入力: nums = [-1,-100,3,99], k = 2
出力: [3,99,-1,-100]
説明: 
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) {
        // 解法 1
        var times = k
        while (times > 0) {
            let last = nums.removeLast()
            nums.insert(last, at: 0)
            times -= 1
        }
    }

最終結果に達することができますが、アルゴリズムとしては不十分で、reverseArray がありません。

解法 2：

reverseArray のロジックは、例えば nums=[1, 2, 3, 4, 5, 6, 7], key = 3 の場合、[1, 2, 3, 4] を回転させて [4, 3, 2, 1] を得て、[5, 6, 7] を回転させて [7, 6, 5] を得て、次に [4, 3, 2, 1, 7, 6, 5] を結合し、再度回転させて [5, 6, 7, 1, 2, 3, 4] を得ます。

コードは以下の通りです：


class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        // 解法 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
        }
    }
}