Python算法例21 交错正负数

1. 问题描述

给出一个含有正整数和负整数的数组，将其重新排列成一个正负数交错的数组。

2. 问题示例

给出数组[-1，-2，-3，4，5，6]，重新排序之后，变成[-1，5，-2，4，-3，6]或者其他任何满足要求的答案。

3. 代码实现

使用双指针算法实现。双指针算法是一种常用的数组操作技巧，它通过使用两个指针在数组中同时从头和尾部遍历，来实现一些特定的操作。

def rearrange_array(nums):
    # 将正整数和负整数分别存放在不同的列表中
    positive_nums = [num for num in nums if num > 0]
    negative_nums = [num for num in nums if num < 0]

    result = []
    i, j = 0, 0
    while i < len(positive_nums) and j < len(negative_nums):
        # 先插入一个正���数，再插入一个负整数
        result.append(positive_nums[i])
        result.append(negative_nums[j])
        i += 1
        j += 1

    # 如果正整数或负整数列表还有剩余元素，将其加入结果列表中
    while i < len(positive_nums):
        result.append(positive_nums[i])
        i += 1

    while j < len(negative_nums):
        result.append(negative_nums[j])
        j += 1

    return result
nums = [-1, -2, -3, 4, 5, 6]
result = rearrange_array(nums)
print(result)

这个算法的时间复杂度是O(n)，其中n是数组的长度。

在算法中，我们首先遍历一次数组将正整数和负整数分别存放在两个列表中，然后通过双指针的方式依次插入正整数和负整数到结果列表中。最后，如果正整数或负整数列表还有剩余元素，我们将其加入结果列表中。因此，整个算法的时间复杂度是O(n)。