刷题笔记合集🔗

最少交换次数

问题描述

给定一个整数数组和一个整数 ，请计算将所有小于 的整数组合在一起所需的最少交换次数。组合在一起指满足条件的数字相邻，不要求相邻后在数组中的具体位置。

输入格式

第一行输入一个整数数组，数组元素之间用空格分隔。 第二行输入整数 。

输出格式

输出一个整数，表示最少交换次数。

样例输入1

1 3 1 4 0
2

样例输出1

1

样例输入2

1 6 3 9 8 4 2 5 7
6

样例输出2

2

样例解释

数据范围

• 
• 数组中每个元素的值
• 数组长度

题解

滑动窗口

这道题目可以使用滑动窗口的方法来解决。核心思想是找到一个连续的子数组，使得这个子数组包含了所有小于 的数，并且需要交换的次数最少。

解题步骤如下：

1. 首先统计数组中小于 的元素个数，记为 。这个 就是我们滑动窗口的大小。

2. 初始化最小交换次数 为 ，因为最坏情况下，我们需要交换 次才能将所有小于 的数组合在一起。

3. 使用滑动窗口遍历数组。窗口大小固定为 ，每次移动一个位置。

4. 对于每个窗口，统计窗口内大于等于 的元素个数 。这个数就是将该窗口内的元素全部变为小于 的数所需的交换次数。

5. 更新 ，取 和 中的较小值。

6. 遍历结束后， 就是最终答案。

这个算法的时间复杂度是 ，其中 是数组的长度。我们只需要遍历一次数组，同时滑动窗口也只需要移动 次。

对于给定的数据范围（数组长度最大为 ），这个算法是高效的，可以在合理的时间内得出结果。

参考代码

• Python

def getMinSwapCount(arr, k):
    # 统计小于k的数组元素个数
    count = sum(1 for x in arr if x < k)
    
    # 初始化最少交换次数
    minSwapCount = count
    
    # 初始化滑动窗口内大于等于k的元素个数
    tmpSwapCount = sum(1 for x in arr[:count] if x >= k)
    
    # 更新最少交换次数
    minSwapCount = min(minSwapCount, tmpSwapCount)
    
    # 滑动窗口
    for i in range(1, len(arr) - count + 1):
        # 移除窗口左侧元素的影响
        if arr[i - 1] >= k:
            tmpSwapCount -= 1
        # 添加窗口右侧新元素的影响
        if arr[i + count - 1] >= k:
            tmpSwapCount += 1
        # 更新最少交换次数
        minSwapCount = min(minSwapCount, tmpSwapCount)
    
    return minSwapCount

# 读取输入
arr = list(map(int, input().split()))
k = int(input())

# 计算并输出结果
print(getMinSwapCount(arr, k))

• C

#include <stdio.h>
#include <stdlib.h>

int getMinSwapCount(int* arr, int arrSize, int k) {
    // 统计小于k的数组元素个数
    int count = 0;
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] < k) count++;
    }
    
    // 初始化最少交换次数
    int minSwapCount = count;
    
    // 初始化滑动窗口内大于等于k的元素个数
    int tmpSwapCount = 0;
    for (int i = 0; i < count; i++) {
        if (arr[i] >= k) tmpSwapCount++;
    }
    
    // 更新最少交换次数
    minSwapCount = (tmpSwapCount < minSwapCount) ? tmpSwapCount : minSwapCount;
    
    // 滑动窗口
    for (int i = 1; i <= arrSize - count; i++) {
        // 移除窗口左侧元素的影响
        if (arr[i - 1] >= k) tmpSwapCount--;
        // 添加窗口右侧新元素的影响
        if (arr[i + count - 1] >= k) tmpSwapCount++;
        // 更新最少交换次数
        minSwapCount = (tmpSwapCount < minSwapCount) ? tmpSwapCount : minSwapCount;
    }
    
    return minSwapCount;
}

int main() {
    int arr[100000];  // 假设最大数组长度为100000
    int arrSize = 0;
    int k;
    
    // 读取输入数组
    int num;
    while (scanf("%d", &num) == 1) {
        arr[arrSize++] = num;
        if (getchar() == '\n') break;
    }
    
    // 读取k值
    scanf("%d", &