百度2023秋招面试算法真题解析
题目描述
小红有一个长度为n的排列，她可以选择两个位置，然后交换两个位置的数。
她想知道能否通过最多一次交换，使得存在一个连续子段，是长度为k的排列。
排列是指一个长度为 len 的整数数组，数组中包含1到len的每个数，且每个数只出现一次。
输入描述
第一行两个整数n,k，表示排列长度和连续子段长度。
第二行n个整数a1, a2, ..., an，表示排列。
1 <= k <= n <= 10^5
输出描述
如果能够通过最多一次交换，存在一个连续子段是排列，输出YES，并输出交换的位置:先输出一个整数x (0 <= x <= 1)，然后输出x行，每行两个整数u, v，表示交换位置u, v (u < v)
否则输出NO。
示例
输入
5 3
1 2 3 4 5
输出
YES
0
解题思路
本题看似很复杂，实际上由于我们要找的是一个固定长度为k的滑动窗口，因此可以直接使用固定滑窗的方法来解答。
一个长度为k的排列，其中一定包含的是1到k一共k个数，由于最多可以交换一次，我们可以允许固定滑窗中包含至多一个大于k的数。故我们可以构建一个哈希表dic，用于储存滑窗中所有大于k的数以及其下标，如果在滑动过程中，发现dic的长度小于等于1，则说明此时固定滑窗只包含至多一个大于k的数，这个数可以通过与其他的某个数进行交换，来使得该滑窗变成一个长度为k的排列。
滑窗三问
Q1：对于每一个右指针right所指的元素right_num，做什么操作？
Q2：什么时候要令左指针left右移？对于left所指的元素left_num，要做什么操作？
Q3：什么时候进行ans的更新？如何更新？
滑窗三答
A1：若right_num大于k，则将其下标right计入哈希表dic中，即dic[right_num] = right
A2：在固定滑窗中，left始终为right-N。若left_num大于k，则需要将其在dic中所储存键值对删除，即del dic[left]。
A3：当发现len(dic) <= 1时，说明此时此时固定滑窗可以至多一次交换，使得该滑窗变成一个长度为k的排列。此时退出循环，寻找窗口中缺失的那个数的下标。
注意在更新答案时，存在一种极为特殊的情况需要判断：
当len(dic) == 1，且left恰好指向的是窗口中大于k的数，right+1恰好指向的是需要交换的数，那么窗口[left+1，right+1]是可以不通过交换就构建长度为k的排列的，所以此时应该输出交换次数为0。
代码
# 根据dic的情况，获取答案的函数
def get_ans(nums, dic, right, k):
x, first, second = 0, 0, 0
# 若dic长度为0，说明此时固定滑窗就是一个长度为k的排列
# 交换次数x为0，无需做任何修改。
# 若dic长度为1，需要做以下判断
if len(dic) == 1:
# 第一个数字的位置，为dic中唯一一个键值对的value
first = list(dic.values())[0]
# 长度为k的排列的和可以用等差数列求和公式获得，记为A
# 固定窗口的和可以直接计算，记为B
# 窗口中多出来的数字，记为C
# 窗口中缺失的数字num_miss，为A-(B-C)
num_miss = (1+k)*k//2 - sum(nums[right-k+1:right+1]) + list(dic.keys())[0]
# 找到num_miss在nums中的下标
second = nums.index(num_miss)
# 特殊情况判断：
# 若此时second的位置在窗口右边界right的下一个位置right+1
# 同时first的位置在窗口左边界right-k+1的位置
# 说明下一个窗口可以无需进行交换，就可以获得长度为k的排列
if second == right+1 and first == right-k+1:
x = 0
else:
x = 1
return x, first, second
n, k = map(int, input().split())
nums = list(map(int, input().split()))
# 初始化交换次数为任意一个大于1的数
x = 2
# 构建哈希表，储存固定滑窗中，所有大于k的元素的下标
dic = {num: i for i, num in enumerate(nums[:k]) if num > k}
# 若第一个固定滑窗就满足题意，则直接获得答案
if len(dic) <= 1:
# 第一个窗口的有边界right = k-1
x, first, second = get_ans(nums, dic, k-1, k)
else:
for right, right_num in enumerate(nums[k:], k):
# A1
if right_num > k:
dic[right_num] = right
# A2
left = right - k
left_num = nums[left]
if left_num > k:
del dic[left_num]
# A3
if len(dic) <= 1:
x, first, second = get_ans(nums, dic, right, k)
break
# 根据最终得到的x的结果，输出答案
if x <= 1:
print("YES")
if x == 1:
print(1)
# 先输出小的位置，再输出大的位置
if first > second:
first, second = second, first
print("{} {}".format(first, second))
else:
print(0)
else:
print("NO")
腾讯云开发者
