我尝试解决 geeksforgeeks.org 关于"交替重新排列数组"的问题，在尝试示例输入时，我没有收到任何错误，但是当我尝试提交它时，我收到"内存错误">
test_cases = "1"
for _ in range(int(test_cases)):
new_array = []
array_size = int("89")
array = list(map(int, "1 9 16 18 72 88 98 100 127 128 150 155 160 174 185 196 198 200 218 226 267 270 279 284 299 309 326 335 335 351 355 369 383 394 399 400 413 422 422 429 438 440 446 483 507 529 529 542 553 556 567 571 578 594 611 640 642 652 658 658 663 673 694 717 723 736 762 763 775 777 778 784 806 816 828 851 853 854 889 891 911 932 953 955 958 973 977 986 998 ".split()))
while len(array) != 0:
if len(array) == 1:
new_array.append(array[0])
array.remove(array[0])
else:
max_array_value = max(array)
min_array_value = min(array)
new_array.append(max_array_value)
new_array.append(min_array_value)
array.remove(max_array_value)
array.remove(min_array_value)
*旁注：让我们忽略为什么我以字符串格式而不是整数使用它，因为我试图从 geeksforgeeks.org 复制输入。
当前代码仅适用于小数组，而不适用于非常大的数组。当我尝试创建超过 100 个整数的列表时，它会给我错误。我想知道是否有解决此类问题的解决方法？
def rearrange(arr, n):
k,j=1,1
a=[0]*n
for i in range(0,n):
if i%2==0:
a[i]=arr[n-k]
k=k+1
else:
a[i]=arr[i-j]
j=j+1
for i in range(n):
arr[i]=a[i]
下面提到的解决方案解决了O(N)时间复杂度和O(1)空间复杂度中的问题，而无需使用"在一个位置存储2个值的概念"。此外，该算法还可以处理重复值和浮点值，因为输入列表是非递减排序的，并且仅由正实数组成。
PS：如果您愿意，可以稍微修改我的算法，使其也适用于负值。
请不要因为查看代码而感到害怕。实现非常简单.
算法可能有点难以理解。
def reArrange(arr, print_arr_state=True):
# arr: non-decreasingly sorted list of positive floats/ints
length = len(arr)
for i in range(length):
if arr[i] > 0:
cycler(arr, i, length, print_arr_state)
arr[i] = abs(arr[i]) # This is the tricky part
# printing the array after every iteration
if print_arr_state:
print('after', i, 'th iteration:', arr)
def cycler(arr, start_index, length, print_cycler_array=True):
if print_cycler_array:
print('cycler function:', arr, end=' ---> ')
half_length_index = length // 2
swap_index = start_index
current_value = arr[start_index]
while True:
if swap_index < half_length_index:
swap_index = 2 * swap_index + 1
else:
swap_index = 2 * (length - 1 - swap_index)
# Placing the current value at swap_index and making the making current_value variable refer to the value which was at swap_index
swap_value = arr[swap_index]
arr[swap_index] = -1 * current_value # -1 * ?? This is the tricky part of the algo
current_value = swap_value
# cycler function will not stop until the simple cycle is complete
# simple cycle is complete when swap_index == start_index
if swap_index == start_index:
if print_cycler_array:
print(arr)
return
给出输入 (input_array) 和调用重新排列函数：
input_array = [0.1, 2, 3.2, 3.3, 3.3, 4, 5.7, 5.7, 6.8, 7, 8, 9]
reArrange(input_array)
输出：
answer_array = [9, 0.1, 8, 2, 7, 3.2, 6.8, 3.3, 5.7, 3.3, 5.7, 4]
了解算法
算法的棘手部分：
每个值正好属于 1 个循环，这个循环是一个简单的循环(图中的简单循环与复杂循环)。循环器函数的一次执行对应于一个循环，这也是一个简单的循环。
每当我在循环中覆盖一个值时，我都会将其乘以 -1(以表示它被覆盖)并将其存储在输入数组本身中。 在reArrange函数循环的第 i 次迭代中，如果我发现第 i 个值为负数，我会得到一个指示，指示该值是为某个第 j 次迭代执行的循环的一部分(其中 j <i)，因此我不调用>循环器函数这个值。但是，如果此值为正(表示到目前为止执行的循环中没有一个覆盖此值)，则意味着它尚未被覆盖，因此应使用循环器函数在第 i 次迭代中覆盖。
但是等等！，如果我将所有值乘以 -1，我的最终答案将是-1 *correct_answer_array。为了解决这个问题，一种解决方案是重申我的answer_array(最初是input_array的，现在已转换为我的answer_array)并获取每个值的绝对值，或者我可以在我的第一次也是唯一一次迭代(reArrange函数的循环)期间做同样的事情，方法是在移动到第 i+1 次迭代之前获取值的绝对值。
一些有效的问题
这篇文章中我没有介绍这个算法的几个方面。让我以问题的形式向您介绍其中的一些方面：
- 循环仪功能的while回路是否保证终止？
- 为什么我们不应该多次覆盖一个价值？
- 我们如何处理负输入值(如果有的话)？
- 单个周期不足以涵盖input_array的所有值吗？(循环器函数的一次调用不足以覆盖所有值)？
提示：例如：1 2 3 4 5 6 7，此示例将导致 3 个周期。(循环仪函数将调用三次) - 在单次调用循环器函数期间会发生什么？
提示：作为此循环一部分的每个值都会移动到它应该在correct_answer_array中的位置。一旦值位于正确的位置，就不应再次对其进行干扰。
该算法是一种全新的原创方法，因此 验证它的人数越多，它被接受为 比"在一个位置存储两个值概念">更好的选择。
请访问本页底部的评论部分(GeeksforGeeks)以查看算法的试运行。请确保您阅读了我的所有评论，因为它在那里部分损坏。