求将所有≥K的元素聚集在一起所需的最少交换次数

嘿，这个问题其实可以用滑动窗口的思路高效解决，我来一步步给你拆解清楚，保证你能看懂：

核心思路 #

首先得明确：我们最终要把所有≥K的元素凑成连续的一段，这段的长度必然等于数组中≥K的元素总数（记为count_ge_k）。那最少交换次数的本质是什么？就是找到一段长度为count_ge_k的连续子数组，其中已经包含的≥K的元素越多，需要交换的次数就越少——因为剩下的空缺只需要用外面的≥K元素补进来，每次交换能填补一个空缺。

所以步骤很清晰：

• 先统计数组里一共有多少个≥K的元素，记为count_ge_k。如果这个数是0（没元素需要凑）或者等于数组长度（已经都凑好了），直接返回0就行。
• 用固定大小为count_ge_k的滑动窗口遍历数组，计算每个窗口里已经存在的≥K元素的数量，记录这个数量的最大值max_in_window。
• 最少交换次数 = count_ge_k - max_in_window——因为窗口里已经有max_in_window个符合要求的元素，剩下的位置需要交换进来，每次交换解决一个位置，所以次数就是两者的差值。

举个例子理解 #

比如数组是[1,3,2,4,5]，K=3：

• 首先统计count_ge_k：3、4、5这3个元素≥3，所以总数是3。
• 滑动窗口大小固定为3：
  • 第一个窗口[1,3,2]：只有1个≥3的元素（3）
  • 第二个窗口[3,2,4]：有2个≥3的元素（3、4）
  • 第三个窗口[2,4,5]：有2个≥3的元素（4、5）
• 最大的max_in_window是2，所以最少交换次数是3-2=1——比如把1和4交换，数组就变成[4,3,2,1,5]，或者把2和5交换变成[1,3,5,4,2]，都能让所有≥3的元素聚在一起，只需要1次交换。

代码实现（Python） #

def min_swaps_to_group(arr, k):
    # 统计数组中≥K的元素总数
    count_ge_k = sum(1 for num in arr if num >= k)
    n = len(arr)
    
    # 特殊情况：没有需要聚集的元素，或者已经全部聚集
    if count_ge_k == 0 or count_ge_k == n:
        return 0
    
    # 初始化第一个窗口的符合条件元素数量
    current_valid = sum(1 for num in arr[:count_ge_k] if num >= k)
    max_valid = current_valid
    
    # 滑动窗口遍历剩余元素
    for i in range(count_ge_k, n):
        # 移除窗口左侧的元素，如果它是符合条件的，当前计数减1
        if arr[i - count_ge_k] >= k:
            current_valid -= 1
        # 加入窗口右侧的元素，如果符合条件，当前计数加1
        if arr[i] >= k:
            current_valid += 1
        # 更新最大值
        if current_valid > max_valid:
            max_valid = current_valid
    
    # 计算最少交换次数
    return count_ge_k - max_valid

# 测试示例
test_arr = [1,3,2,4,5]
test_k = 3
print(min_swaps_to_group(test_arr, test_k))  # 输出：1

复杂度分析 #

• 时间复杂度：O(N)，只需要遍历数组两次（一次统计总数，一次滑动窗口），非常高效。
• 空间复杂度：O(1)，只用到了几个变量，不需要额外的空间。

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