Pythonで配列をジグザグ配列に変換する!最小の操作回数を求めるアルゴリズム

問題の概要

整数の配列 nums が与えられます。ここでいう「1回の操作」とは、任意の要素を1つ選び、その値を1だけ減らすことを指します。

配列 A が「ジグザグ配列」であるとは、以下の条件のいずれか一方を満たすことです。

• 偶数インデックスの要素が隣接要素より大きいパターン: A[0] > A[1] < A[2] > A[3] < A[4] > ... という形になります。
• 奇数インデックスの要素が隣接要素より大きいパターン: A[0] < A[1] > A[2] < A[3] > A[4] < ... という形になります。

この問題では、与えられた配列 nums をジグザグ配列へ変換するために必要な最小の操作回数を求めます。

例えば、配列が [1,2,3] の場合、答えは 2 になります。2 を 0 に減らすか、あるいは 3 を 1 に減らすことでジグザグ配列にできるためです。

解き方のアプローチ

ポイントは、ジグザグ配列の形状は2パターンしか存在しないという点です。「偶数番目が山になるパターン」と「奇数番目が山になるパターン」のどちらか一方のみです。それぞれのパターンについて必要な操作回数を計算し、小さい方を採用すればよいことになります。

具体的には、以下の手順で解きます。

• solve() メソッドを定義します。引数として nums(配列)と start(開始インデックス)を受け取ります。
• カウンタ k を 0 で初期化します。
• i を start から配列の長さまで、2ずつ増やしながらループします。
  • left: i - 1 < 0 の場合は 100000(境界外を表す十分に大きな値)、それ以外は nums[i - 1]
  • right: i + 1 >= len(nums) の場合は 100000、それ以外は nums[i + 1]
  • temp = min(left, right) - 1 - nums[i] を計算します。
  • temp < 0 の場合、つまり現在の要素が隣接要素より大きすぎる場合は、k += abs(temp) として必要な減算回数を加算します。
• 最後に k を返します。
• メイン処理では、まず ans = solve(nums, 0) を計算し、続いて ans = min(ans, solve(nums, 1)) として2つのパターンのうち小さい方を結果として返します。

Pythonでの実装例

以下の実装を見ると、処理の流れがより理解しやすくなります。

class Solution(object):
    def solve(self,nums,start):
        k = 0
        for i in range(start,len(nums),2):
            left = 100000 if i-1<0 else nums[i-1]
            right = 10000 if i+1>=len(nums) else nums[i+1]
            temp= (min(left,right)-1 - nums[i])
            if temp<0:
                k+=abs(temp)
        return k
    def movesToMakeZigzag(self, nums):
        ans = self.solve(nums,0)
        ans = min(ans,self.solve(nums,1))
        return ans
ob = Solution()
print(ob.movesToMakeZigzag([1,2,3]))

入力

[1,2,3]

出力

2

計算量について

このアルゴリズムは配列を高々2回走査するだけで済むため、時間計算量は O(n)、追加で必要なメモリは O(1) となります。要素を増やす操作が許されておらず「減らす」ことしかできない点に着目すれば、各要素が必要な減算回数は隣接要素との差だけで一意に決まるため、貪欲法で正しい答えが得られる仕組みです。