计算元素上限为3的含重复值数组排序所需最小交换次数的算法

存在时间复杂度为*O(n)*的高效算法，仅需遍历数组两次即可得到结果，完全适配你提到的元素取值上限为3的约束条件。

核心原理 #

排序后的数组天然被划分为三个连续的固定区间：

• 前cnt1位全部为1，cnt1是原数组中1的总个数
• 中间cnt2位全部为2，cnt2是原数组中2的总个数
• 最后cnt3位全部为3，cnt3是原数组中3的总个数

最优交换的核心逻辑是优先处理单次交换可修正两个错位元素的场景，再处理需要两次交换修正三个错位元素的循环错位场景：

1. 先统计所有错位情况：
   • 1区（应该放1的位置）中2的数量记为a、3的数量记为b
   • 2区（应该放2的位置）中1的数量记为c、3的数量记为d
   • 3区（应该放3的位置）中1的数量记为e、2的数量记为f
2. 单次交换可解决的错位：每配对1个1区的2和1个2区的1、1个1区的3和1个3区的1、1个2区的3和1个3区的2，都仅需要1次交换，这部分总交换次数为min(a,c) + min(b,e) + min(d,f)
3. 剩余的错位必然是三类元素循环错位的场景（比如1区有3、2区有1、3区有2），每存在1组这样的循环需要2次交换，剩余的循环组数和abs(a-c)相等，这部分总交换次数为2 * abs(a-c)

你给出的示例刚好全部属于单次交换可解决的场景，最终交换次数为2，和示例结果一致。

代码实现示例（Python） #

def min_swap_count(arr):
    # 统计三类元素的总个数，确定区间边界
    cnt1 = arr.count(1)
    cnt2 = arr.count(2)
    a = b = c = d = e = f = 0
    # 遍历统计各区间错位数量
    for idx, num in enumerate(arr):
        if idx < cnt1:
            if num == 2:
                a += 1
            elif num == 3:
                b += 1
        elif idx < cnt1 + cnt2:
            if num == 1:
                c += 1
            elif num == 3:
                d += 1
        else:
            if num == 1:
                e += 1
            elif num == 2:
                f += 1
    # 计算总交换次数
    single_swap = min(a, c) + min(b, e) + min(d, f)
    cycle_swap = 2 * abs(a - c)
    return single_swap + cycle_swap

# 测试示例
test_arr = [1,3,1,1,2,1,2,3,2,3]
print(min_swap_count(test_arr)) # 输出结果为2

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