大家好，我是程序员小灰，关注我，
每周更新
大厂最新笔试题解析。
今天更新的是
华为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 += 1
-
A[ia_left] < B[ib_left]
。由于此时
A
中最小值小于
B
中的任意一个元素，我们不妨采取
田忌赛马
的策略，让
A[ia_left]
和
B[ib_right]
进行分组，
B
获胜。
if A[ia_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] 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 -= 1
-
A[ia_right] > B[ib_right]
，即以下情况
-
A[ia_right] < B[ib_right]
，即以下情况
