python - 在 Python 中创建 Zigzag 数组的函数

Question

我正在尝试创建一个由正和负整数组成的数组，分别表示北和南的距离位置的 - 我需要以锯齿形顺序查看数组的元素。

这意味着最大成员首先出现，最小成员第二次出现，其余元素在较大成员之间交替出现，从最大和较小成员从最小开始增加。

即数组 [1, 3, 6, 9, -3] 变为 [9, -3, 6, 1, 3]。

我正在尝试完成函数 wiggleArrangeArray，该函数接受一个参数，即一个包含 n 个整数的整数数组。

所需的输入格式、约束和输出格式

我不知道该怎么说

“如果数组中的项大于数组中的其他项，则先显示它。”

“如果该项目小于数组中的其他项目，则第二个显示它。”

“然后在下一个最大的数字和下一个最小的数字之间交替”

def wiggleArrangeArray(intArr):
    for i in intArr
        #if i > other items in intArr
        #display that i at index value 0
        #if i < other items in intArr
        #display that i at index value 1
        #if i < i at index value 0 and > other items in intArr, display it next
        #if i > i at index value 1 and < other items in intArr, display it next
        #repeat last two lines for continuing values

如果可以的话请帮忙。 Here's a link C++ 中的解决方案，但我需要 Python 中的解决方案。谢谢。

编辑:该函数需要进行以下测试:

f = open(os.environ["OUTPUT_PATH"], "w")

_intArr_cnt = int(raw_input())
_intArr_i=0
_intARR = []
while _intArr_i < _intArr_cnt:
    _intArr_item = int(raw_input());
    _intArr.append(_intArr_item)
    _intArr_i+=1

res = wiggleArrangeArray(_intArr);
for res_cur in res:
    f.write( str(res_cur) + "\n" )

f.close()

Answer 1

修改后的 C++ 代码

Note the algorithm you provided does calculate some sort of zigzag, but it is not the zigzag you are looking for. For future reference I will leave it here.

In the C++ code you provided, they only look for a sequences that satisfies a < b > c < d > e < f, you are looking however for a sequence with the 1-max, 1-min, 2-max, 2-min,...

您的链接为您提供了一个解决方案，您可以在 Python 中几乎逐字复制该解决方案。您只需定义一个交换函数:

def swap(arr,i,j):
    t = arr[i]
    arr[i] = arr[j]
    arr[j] = t

接下来只需修改代码即可:

def zigZag(arr):
    n = len(arr)
    # Flag true indicates relation "<" is expected,
    # else ">" is expected.  The first expected relation
    # is "<"
    flag = True

    i = 0
    while i<= n-2:
        if (flag):  # "<" relation expected
            # If we have a situation like A > B > C,
            # we get A > B < C by swapping B and C
            if arr[i] > arr[i+1]:
                swap(arr,i,i+1)
        else: # ">" relation expected
            # If we have a situation like A < B < C,
            #  we get A < C > B by swapping B and C
            if arr[i] < arr[i+1]:
                swap(arr,i,i+1)
        flag = not flag # flip flag
        i += 1

请注意，这相当非Pythonic，因此您可以简单地改进它，例如:

def swap(arr,i,j):
    arr[i],arr[j] = arr[j],arr[i]

def zigZag(arr):
    n = len(arr)
    for i in range(len(arr)-1):
        if not i&1:
            if arr[i] > arr[i+1]:
                swap(arr,i,i+1)
        elif arr[i] < arr[i+1]:
            swap(arr,i,i+1)
    return arr

这里元组赋值用于交换列表中的元素，范围用于迭代索引，我们还可以使用elif 而不是 else 中的 if，并且我通过使用模检查放弃了 flag。

您的之字形函数

您可以简单地通过对列表进行排序来解决问题，并使用两个指针，每次发出最左、最右并向彼此走去。换句话说:

def zigZag(arr):
    srt = sorted(arr)
    left = 0
    right = len(srt)-1
    result = []
    while left < right:
        result.append(srt[right])
        right -= 1
        if left < right:
            result.append(srt[left])
            left += 1
    return result