华为OD机试真题B卷 Python 实现【最少交换次数】，附详细解题思路

目录

• • 一、题目描述
  • 二、输入描述
  • 三、输出描述
  • 四、解题思路
  • 五、解题思路
  • 六、Python算法源码
  • 七、效果展示

一、题目描述

给出数字K，请输出所有小于K的整数组合到一起的最小交换次数。

组合一起是指满足条件的数字相邻，不要求相邻后在数组中的位置。

取值范围：

-100 <= K <= 100

-100 <= 数组中的数值 <= 100

二、输入描述

第一行输入数组：1 3 1 4 0

第二行输入K数值：2

三、输出描述

第一行输出的最少交换次数：1

四、解题思路

利用滑动窗口的思想，窗口大小为所有小于K的整数，然后窗口中大于K的整数是需要替换的次数。

五、解题思路

1. 读取输入的整数数组和目标数值K；
2. 统计数组中小于K的整数个数，记为count；
3. 如果count为1，表示只有一个小于K的整数，不需要交换，直接输出0；
4. 初始化最小交换次数minSwapCount为0；
5. 遍历数组前count个元素，如果元素大于等于K，将minSwapCount加1；
6. 将minSwapCount赋值给临时变量temp；
7. 从第count个元素开始遍历数组，记当前元素为nums[j]，前一个元素为nums[l]，后一个元素为nums[r]，其中l = j - count，r = j；
8. 如果nums[l]大于等于K且nums[r]小于K，表示交换nums[l]和nums[r]可以减少一次交换次数，将temp减1；
9. 如果nums[l]小于K且nums[r]大于等于K，表示交换nums[l]和nums[r]可以增加一次交换次数，将temp加1；
10. 更新最小交换次数minSwapCount为min(minSwapCount, temp)，保留较小的值；
11. 输出最小交换次数minSwapCount；

六、Python算法源码

# 整数组合
nums = input().split(" ")
# 数字K
k = input()

def calculate(nums, k):
    # 统计数组中小于k的整数个数
    count = len([num for num in nums if num < k])

    # 如果只有一个，则不需要交换
    if count == 1:
        return 0

    # 最小交换次数
    minSwapCount = 0
    # 遍历数组前count个元素，如果元素大于等于k，将minSwapCount加1
    for i in range(count):
        if nums[i] >= k:
            minSwapCount += 1

    temp = minSwapCount
    # 从第count个元素开始遍历数组
    for j in range(count, len(nums)):
        # 当前元素为nums[j]，前一个元素为nums[l]，后一个元素为nums[r]
        l = j - count
        r = j
        # 判断是否需要交换nums[l]和nums[r]
        if nums[l] >= k and nums[r] < k:
            # 交换nums[l]和nums[r]可以减少一次交换次数，将temp减1
            temp -= 1
        elif nums[l] < k and nums[r] >= k:
            # 交换nums[l]和nums[r]可以增加一次交换次数，将temp加1
            temp += 1
        # 最小交换次数
        minSwapCount = min(minSwapCount, temp)

    # 返回最小交换次数
    return minSwapCount

# 输出内存池分配结果
print(calculate(nums, k))

七、效果展示

1、输入

1 3 1 4 0
2

2、输出

1

🏆下一篇：华为OD机试真题 Python 实现【相对开音节】【2022Q4 100分】，附详细解题思路

🏆本文收录于，华为OD机试（Python）真题（A卷+B卷）

每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。