1

我正在尝试创建一个正整数和负整数数组，代表一个位置的南北距离-我需要以之字形顺序查看数组的元素。

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

即数组 [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

如果可能，请提供帮助。这是 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()
4

2 回答 2

3

修改后的 C++ 代码

请注意，您提供的算法确实计算了某种锯齿形，但它不是您正在寻找的锯齿形。为了将来参考，我将其留在这里。

在您提供的 C++ 代码中，他们只寻找满足 a < b > c < d > e < f 的序列，但是您正在寻找具有 1-max、1-min、2-max、2- 的序列分钟，...

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

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

这里元组赋值用于交换列表中的元素，arange用于迭代索引，我们还可以在 an 中使用 anelif而不是ifan else，因为我已经放弃了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
于 2017-01-19T20:17:16.370 回答
0

这里是 Python 实现示例。

  1. 以相反的顺序对数据进行排序（9、6、3、1、-3）
  2. 由两个列表 (9, 6) (3, 1, -3) 拆分
  3. 迭代两个（使用 zip_longest）第一个从开始，第二个以相反的顺序 (9, -3), (6, 1) (None, 3)
  4. 解压缩由 zip_longest (chain(*zip...)) 创建的元组，以便获得可迭代数据 (9, -3, 6, 1, None, 3)
  5. 如果列表具有奇数个元素（如果 x 不是 None），则删除 None 值

例子：

from itertools import zip_longest, chain


def zig_zag_array(data):
    data = sorted(data)
    mid = len(data) // 2
    return [
        x for x in chain(*zip_longest(data[mid:][::-1], data[:mid])) if x is not None
    ]

测试：

if __name__ == "__main__":
    data = [1, 3, 6, 9, -3]
    expected = [9, -3, 6, 1, 3]
    output = zig_zag_array(data)
    assert output == expected, f"Odd length: {output=}"

    data = [1, 3, 6, 9, -3, 0]
    expected = [9, -3, 6, 0, 3, 1]
    output = zig_zag_array(data)
    assert output == expected, f"Even length: {output=}"
    print("PASSED")
于 2020-03-08T17:15:55.023 回答