在 Python 中创建之字形数组的函数
Function to Create a Zigzag Array in Python
我正在尝试创建一个 positive 和 negative 整数数组，代表距离 north 和一个位置的 south - 我需要以 zigzag 顺序查看数组的元素。
这意味着最大的成员首先出现，最小的成员第二出现，其余元素在[=38之间交替出现=]较大 成员从最大减少，较小 成员从最小[=51=增加].
即数组 [1, 3, 6, 9, -3] 变为 [9, -3, 6, 1, 3]。
我正在尝试完成函数 wiggleArrangeArray，它接受一个参数，一个包含 n 个整数的整数数组。
必需的输入格式、约束和输出格式
我不知道怎么说
"if the item in the array is larger than the other items in the array, display it first."
"if the item is smaller than the other items in the array, display it second."
"then alternate between the next largest numbers, and the next smallest numbers"
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()
修改后的 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,...
您的 link 为您提供了一个解决方案，您可以将其几乎逐字复制到 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
请注意，这相当 un-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
这里元组赋值用于交换列表中的元素，range用于遍历索引，我们还可以使用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
此处Python实现示例。
- 以相反的顺序对数据进行排序（9、6、3、1、-3）
- 分成两个列表 (9, 6) (3, 1, -3)
- 迭代两者（使用 zip_longest）第一个从头开始，第二个以相反的顺序 (9, -3), (6, 1) (None, 3)
- 解压由 zip_longest (chain(*zip...)) 创建的元组，以便获得可迭代数据 (9, -3, 6, 1, None, 3)
- 删除 None 值以防列表中的元素数量为奇数（如果 x 不是 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")
我正在尝试创建一个 positive 和 negative 整数数组，代表距离 north 和一个位置的 south - 我需要以 zigzag 顺序查看数组的元素。
这意味着最大的成员首先出现，最小的成员第二出现，其余元素在[=38之间交替出现=]较大 成员从最大减少，较小 成员从最小[=51=增加].
即数组 [1, 3, 6, 9, -3] 变为 [9, -3, 6, 1, 3]。
我正在尝试完成函数 wiggleArrangeArray，它接受一个参数，一个包含 n 个整数的整数数组。
必需的输入格式、约束和输出格式
我不知道怎么说
"if the item in the array is larger than the other items in the array, display it first."
"if the item is smaller than the other items in the array, display it second."
"then alternate between the next largest numbers, and the next smallest numbers"
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()
修改后的 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,...
您的 link 为您提供了一个解决方案，您可以将其几乎逐字复制到 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
请注意，这相当 un-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
这里元组赋值用于交换列表中的元素，range用于遍历索引，我们还可以使用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
此处Python实现示例。
- 以相反的顺序对数据进行排序（9、6、3、1、-3）
- 分成两个列表 (9, 6) (3, 1, -3)
- 迭代两者（使用 zip_longest）第一个从头开始，第二个以相反的顺序 (9, -3), (6, 1) (None, 3)
- 解压由 zip_longest (chain(*zip...)) 创建的元组，以便获得可迭代数据 (9, -3, 6, 1, None, 3)
- 删除 None 值以防列表中的元素数量为奇数（如果 x 不是 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")