列表元素重排：将重复元素移至右侧、唯一元素移至左侧（O(n)时间O(1)空间）

给定输入数组input = [1,2,1,3,3,1,2,4]，需要将其重排为out = [1,2,3,4,1,1,2,3]——前半段是所有不同元素按首次出现顺序排列，后半段是剩余重复元素按原顺序排列。以下是满足O(n)时间、O(1)空间要求的解法：

核心思路 #

利用输入元素均为正整数的特性，直接在原数组上做标记和重排，无需额外哈希表或数组：

1. 标记元素出现次数：通过给数组对应索引位置的值累加数组长度，实现用原数组存储每个元素的出现次数（取模可恢复原值，整除可获取次数）。
2. 提取首次出现元素：遍历数组，将每个元素的首次出现实例移到数组前半段，同时更新标记避免重复提取。
3. 提取重复元素：再次遍历数组，将剩余的重复元素按原顺序移到数组后半段。

代码实现（Python） #

def rearrange_array(arr):
    n = len(arr)
    # 步骤1：用数组自身标记每个元素的出现次数
    for x in arr:
        idx = x - 1
        arr[idx] += n
    
    # 步骤2：提取首次出现的元素到前半段
    pos = 0
    for x in arr:
        orig_x = x % n
        cnt = arr[orig_x - 1] // n
        if cnt > 0:
            arr[pos] = orig_x
            pos += 1
            arr[orig_x - 1] -= n  # 减少计数，避免重复提取
    
    k = pos  # 记录不同元素的数量
    # 步骤3：提取重复元素到后半段
    pos = k
    for x in arr:
        orig_x = x % n
        cnt = arr[orig_x - 1] // n
        if cnt > 0:
            arr[pos] = orig_x
            pos += 1
            arr[orig_x - 1] -= n
    
    return arr

# 测试示例
input_arr = [1,2,1,3,3,1,2,4]
output_arr = rearrange_array(input_arr.copy())  # 用copy避免修改原输入
print(output_arr)  # 输出: [1,2,3,4,1,1,2,3]

复杂度分析 #

• 时间复杂度：O(n)，共3次线性遍历数组，每次遍历均为O(n)操作，总时间复杂度为线性。
• 空间复杂度：O(1)，仅使用了n、pos、k等常数个额外变量，未使用任何额外的数组或哈希表结构。

注意事项 #

• 该解法依赖输入元素为正整数且值不超过数组长度的前提。若元素范围超出数组长度，可改用「取反标记首次出现」的方式（需确保元素非零）。
• 若需保留原输入数组，只需传入数组副本即可，不影响空间复杂度的计算。

内容的提问来源于stack exchange，提问作者harekrushna mishra