求最少交换次数排序二进制数组的最优算法及优化方案

核心原理 #

二进制数组排序后的结构是固定的：前cnt0位全部为0，剩余位全部为1，其中cnt0是原数组中0的总个数。
最少交换次数等价于前cnt0位中出现的1的总个数：每一个前半段的1都对应后半段的一个0，单次交换即可让两个元素同时归位，没有多余操作。

以你给出的示例[0,0,0,1,0,1,0]验证：

• 统计得数组总共有5个0，因此前5位应该全部为0
• 前5位中只有1个1（索引3位置），因此最少交换次数为1，和实际需求一致。

优化点说明 #

你当前使用的冒泡排序时间复杂度为O(n²)，仅适合小规模数组。以下方案时间复杂度为O(n)，空间复杂度为O(1)，是该场景下的最优解法，数组长度越大性能提升越明显。

Python实现 #

仅计算最少交换次数 #

def min_swap_binary_arr(arr: list[int]) -> int:
    cnt0 = arr.count(0)
    swap_count = 0
    # 统计前cnt0位中1的数量
    for i in range(cnt0):
        if arr[i] == 1:
            swap_count += 1
    return swap_count

# 测试示例
arr = [0,0,0,1,0,1,0]
print(min_swap_binary_arr(arr)) # 输出：1

带排序的完整实现（不修改原数组） #

def sort_binary_arr_min_swap(arr: list[int]) -> tuple[list[int], int]:
    arr = arr.copy()
    cnt0 = arr.count(0)
    left = 0
    right = len(arr) - 1
    swap_count = 0
    while left < cnt0 and right >= cnt0:
        # 找前半段需要交换的1
        while left < cnt0 and arr[left] == 0:
            left += 1
        # 找后半段需要交换的0
        while right >= cnt0 and arr[right] == 1:
            right -= 1
        if left < cnt0 and right >= cnt0:
            arr[left], arr[right] = arr[right], arr[left]
            swap_count += 1
            left += 1
            right -= 1
    return arr, swap_count

# 测试示例
arr = [0,0,0,1,0,1,0]
sorted_arr, cnt = sort_binary_arr_min_swap(arr)
print(sorted_arr) # 输出：[0, 0, 0, 0, 0, 1, 1]
print(cnt) # 输出：1

C++ 参考实现 #

#include <vector>
#include <iostream>
using namespace std;

int minSwapBinaryArr(vector<int>& arr) {
    int cnt0 = 0;
    for (int num : arr) {
        if (num == 0) cnt0++;
    }
    int swapCnt = 0;
    for (int i = 0; i < cnt0; i++) {
        if (arr[i] == 1) swapCnt++;
    }
    return swapCnt;
}

int main() {
    vector<int> arr = {0,0,0,1,0,1,0};
    cout << minSwapBinaryArr(arr) << endl; // 输出：1
    return 0;
}

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