华为2023秋招笔试真题解析
- 2026-10-30 19:46:50
来源丨经授权转自 吴师兄学算法（ID：CXYxiaowu）
作者丨吴师兄
今天更新的是华为2023秋招算法面试题。
数字序列比大小
题目描述
A，B两个人玩一个数字比大小的游戏，在游戏前，两个人会拿到相同长度的两个数字序列，两个数字序列不相同的，且其中的数字是随机的。A，B各自从数字序列中挑选出一个数字进行大小比较，赢的人得1分，输的人扣1分，相等则各自的分数不变。用过的数字需要丢弃。求A可能赢B的最大分数。
输入描述
输入数据的第1个数字表示数字序列的长度N，后面紧跟着两个长度为N的数字序列。
输出描述
A可能赢B的最大分数
示例
输入
3
4 8 10
3 6 4
输出
3
解题思路
这道题很明显是一道贪心的题目。由于平局情况的出现，本题难点在于我们如何地选择策略。
首先需要将两个数组各自排序，方便考虑。我们设置四个指针ia_left，ia_right，ib_left，ib_right，分别指向A、B数组中尚未比较过的元素的最小值和最大值。其初始化为
ia_left = 0
ib_left = 0
ia_right = n-1
ib_right = n-1
在一个while循环中，比较A和B中尚未比较过元素的最小值，即A[ia_left]和B[ib_left]。若
A[ia_left] > B[ib_left]。由于选择B中的其他数字，可能会导致A[ia_left]无法获胜，故选择该组进行比较，A获胜。if A[ia_left] > B[ib_left]:
ans += 1
ia_left += 1
ib_left += 1A[ia_left] < B[ib_left]。由于此时A中最小值小于B中的任意一个元素，我们不妨采取田忌赛马的策略，让A[ia_left]和B[ib_right]进行分组，B获胜。
if A[ia_left] < B[ib_left]:
ans -= 1
ia_left += 1
ib_right -= 1
A[ia_left] == B[ib_left]。这是最复杂的情况，我们需要再嵌套一个while循环，以考虑A和B中尚未比较过元素的最大值，即A[ia_right]和B[ib_right]情况。若暂时无法在飞书文档外展示此内容
此时固然可以令
A[ia_left]和B[ib_left]、A[ai_right]和B[ib_right]两两分组，但剩余元素的比较可能会让A的失利场次增多。故仍然应该选择
A[ia_left]和B[ib_right]进行分组，此时丢失的分数，可能能够在A[ia_right]的其他配对中获取回来。由于此时
ia_left前进，故内层while循环可以退出。显然这种情况可以和上一种情况
A[ia_right] < B[ib_right]合并在一起，即要注意有可能出现
A[ia_left] == A[ia_right] == B[ib_left] == B[ib_right]的情况，故需要多加一句特殊判断。if A[ia_right] <= B[ib_right]:
if A[ia_left] < B[ib_right]:
ans -= 1
ia_left += 1
ib_right -= 1
break暂时无法在飞书文档外展示此内容
由于此时
B[ib_right]大于A中的任何一个元素，A无论如何配对都必输，故仍然维持着田忌赛马的策略令A[ia_left]和B[ib_right]分组，获胜。由于此时
ia_left前进，故内层while循环可以退出。暂时无法在飞书文档外展示此内容
若此时令
A[ia_left]和B[ib_right]分组，由于A[ia_right]无论怎么配对都是必胜，但A[ia_left]原本可以平局的配对现在却输了，故不能采取这样的策略。故让
A[ia_right]和B[ib_right]分组，A[ia_right]获胜。由于
A[ia_left] == B[ib_left]的情况仍然存在，故此时内层的while循环不能退出。if A[ia_right] > B[ib_right]:
ans += 1
ia_right -= 1
ib_right -= 1A[ia_right] > B[ib_right]，即以下情况A[ia_right] < B[ib_right]，即以下情况A[ia_right] == B[ib_right]，即以下情况
本题核心逻辑其实就是田忌赛马，在A[ia_left]必定无法胜利的情况下（无论是必输还是可能平局），都尽量地让A[ia_left]和B[ib_right]配对。
代码
# 作者：闭着眼睛学数理化
# 微信：278166530
# 来自专栏《玩转大厂面试真题》
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# 分别对A和B数组进行排序
A.sort()
B.sort()
# 设置四个指针
ia_left = 0
ib_left = 0
ia_right = n-1
ib_right = n-1
ans = 0
# 进行循环，
# 由于每次判断，A和B中的指针必定均移动一位
# 故此处只需设置一个退出循环条件即可
while ia_left < ia_right:
# A中最小值【大于】B中最小值的情况
if A[ia_left] > B[ib_left]:
ans += 1
ia_left += 1
ib_left += 1
# A中最小值【小于】B中最小值的情况
elif A[ia_left] < B[ib_left]:
ans -= 1
ia_left += 1
ib_right -= 1
# A中最小值【等于】B中最小值的情况
else:
# 内层while循环
while ia_left < ia_right:
# A中最大值【大于】B中最大值的情况
if A[ia_right] > B[ib_right]:
ans += 1
ia_right -= 1
ib_right -= 1
# A中最大值【小于等于】B中最大值的情况
else:
if A[ia_right] <= B[ib_right]:
if A[ia_left] < B[ib_right]:
ans -= 1
ia_left += 1
ib_right -= 1
break
# 退出循环时，存在ia_left == ia_right，ib_left == ib_right
# 故需要再重新判断最后一组数组A[ia_left]和B[ib_left]
if A[ia_left] > B[ib_left]:
ans += 1
elif A[ia_left] < B[ib_left]:
ans -= 1
print(ans)
时空复杂度
时间复杂度：O(NlogN)。排序所需的时间复杂度。在while循环中，两个列表中的每个元素只会经过一次。
空间复杂度：O(1)。仅需四个指针，若干常数变量。
点分享
点点赞
点在看
