1

数値の配列 (またはこの場合は pandas シリーズ) を指定すると、最長のウィグル部分配列が返されます。ウィグル配列は、数字が方向を交互に変えるもので、厳密に上下します。いえ

Input: [10, 22, 9, 33, 49, 50, 31, 60, 15]

Output: [49, 50, 31, 60, 15]

配列は順番に形成する必要があります。つまり、値をスキップして配列を形成することはできません。

私の単純なブルート フォース アプローチは以下にあります。これを機能させるのに苦労しています。任意のヒント？

def zigzag(arr):
    result = pd.Series([])
    for i in range(len(arr)-2):
         if arr[i:i+3] != sorted(arr[i:i+3]) and arr[i:i+3] != sorted(arr[i:i+3], reverse = True): # no three points increase or decrease
            result = result.append(pd.Series(arr[i:i+3], index = list(range(i, i+3))))
            result = result.loc[~result.index.duplicated(keep='first')] 
         else:
            result = pd.Series([])
    return result
4

1 に答える 1

1

ジグザグ条件を繰り返してチェックし、条件を破る要素に到達するまで要素を貪欲に取り、答えを最大化することにより、線形の複雑さを持つ貪欲なソリューションを実装できます(条件を破らない範囲)現在の要素 (条件を破った要素) から操作を繰り返します。

要素が条件を破る場合、その要素の前の範囲とその後の範囲を含むより良い答えがないため、これは機能します。

私は自分のマシンでコードを実行していませんが、例を次に示します（コメントに従ってください）：

def zigzag(arr):
    mx, cur, lst, op = 0, 0, -1, 0
    st, en = 0, 0
    ans = 0
    for i, x in enumerate(arr):
        # if its the first element we take it greedily
        if lst == -1:
            lst = x
            st = i
        # else if lst is the first element taken then decide which direction we need next
        elif op == 0:
            if x > lst:
                op = 1
            elif x < lst:
                op = -1
            # if current element is equal to last taken element we stop and start counting from this element
            else:
                # check if current range is better than previously taken one
                if i-st > mx:
                    mx = i-st
                    ans = st
                    en = i
                st = i
                op = 0

            lst = x
        else:
            # if direction meets the inequality take the current element
            if (op == 1 and x < lst) or (op == -1 and x > lst):
                op *= -1
                lst = x
            # otherwise, check if the current range is better than the previously taken one
            else:
                if i-st > mx:
                    mx = i-st
                    ans = st
                    en = i
                st = i
                lst = x
                op = 0
    # if starting index is greater than or equal to the last, then we have reached the end without checking for maximum range
    if st >= en:
        if len(arr)-st > en-ans:
            ans = st
            en = len(arr)
    result = [arr[i] for i in range(ans, en)]
    return result

print(zigzag([10, 22, 9, 33, 49, 50, 31, 60, 15]))
# [49, 50, 31, 60, 15]
于 2019-11-08T20:53:37.567 に答える