数组正负元素交替重排且保序的代码性能优化咨询

优化方案：解决正负交替数组重排的超时问题 #

你的核心问题应该是原代码用了O(n²)级别的元素移动逻辑（比如每次找到目标元素后逐个后移中间元素），对于1e6规模的数组来说，这样的时间复杂度完全无法承受。下面是针对这个问题的高效优化思路和实现：

1. 核心优化方向：避免重复遍历+高效元素移动 #

（1）用指针跟踪目标元素，避免重复查找

维护两个指针pos_ptr和neg_ptr，分别记录当前已遍历到的下一个正元素、负元素的位置。每次需要找目标元素时，直接从对应指针位置开始，不用从当前位置重新遍历，把查找的总时间降到O(n)。

（2）用底层优化的操作替代手动循环移动元素

在Python中，手动循环移动元素的开销极大，而切片赋值是底层C实现的操作，速度快几十倍甚至上百倍。用切片赋值完成元素的右旋转，能大幅提升大数组的处理效率。如果是C++等编译型语言，可以用memmove函数实现同样的高效移动。

2. 完整优化代码示例（Python） #

def rearrange_alternate(arr):
    n = len(arr)
    pos_ptr = 0  # 跟踪下一个待使用的正元素位置
    neg_ptr = 0  # 跟踪下一个待使用的负元素位置
    i = 0
    
    while i < n:
        if i % 2 == 0:
            # 偶数位置必须放正元素
            if arr[i] > 0:
                pos_ptr = max(pos_ptr, i + 1)
                i += 1
            else:
                # 找到下一个正元素
                while pos_ptr < n and arr[pos_ptr] <= 0:
                    pos_ptr += 1
                # 题目保证正负数量相等，不会出现找不到的情况
                # 旋转元素：将pos_ptr位置的正元素移到i位置
                temp = arr[pos_ptr]
                arr[i+1:pos_ptr+1] = arr[i:pos_ptr]
                arr[i] = temp
                pos_ptr += 1
                i += 1
        else:
            # 奇数位置必须放负元素
            if arr[i] < 0:
                neg_ptr = max(neg_ptr, i + 1)
                i += 1
            else:
                # 找到下一个负元素
                while neg_ptr < n and arr[neg_ptr] >= 0:
                    neg_ptr += 1
                # 旋转元素：将neg_ptr位置的负元素移到i位置
                temp = arr[neg_ptr]
                arr[i+1:neg_ptr+1] = arr[i:neg_ptr]
                arr[i] = temp
                neg_ptr += 1
                i += 1
    return arr

# 测试示例
input_arr = [1,2,3,-1,-2,-3,1,-4,-7,6,-5,2]
print(rearrange_alternate(input_arr))
# 输出: [1, -1, 2, -2, 3, -3, 1, -4, 6, -7, 2, -5]

3. 为什么这个方案高效？ #

• 时间复杂度：O(n)。每个元素最多被访问一次（查找阶段），最多被移动一次（旋转阶段），总操作次数是线性的，完全适配1e6规模的数组。
• 空间复杂度：O(1)。全程在原数组上操作，没有使用任何额外数据结构，符合题目要求。
• 语言层面优化：用切片赋值替代Python手动循环，利用底层C实现的操作大幅降低了循环开销，这是解决Python大数组处理超时的关键。

针对编译型语言的额外优化 #

如果你的代码是用C++/Java实现的，可以用内存拷贝函数（比如C++的memmove）替代手动循环移动元素，同样能获得接近底层的执行效率。

内容的提问来源于stack exchange，提问作者sahil mehta