板球比赛中两队球员得分数组的第二高值求解咨询

高效解法思路 #

没必要对数组排序，通过一次遍历两个数组，维护max1（当前最高分）和max2（当前第二高分）两个变量即可，时间复杂度为O(n+m)（n、m分别为两个数组长度），比排序法更高效。

具体操作步骤：

1. 初始化max1和max2为负无穷（兼容得分是0或负数的场景）。
2. 遍历第一个数组的每个元素：
   • 如果当前元素大于max1：把max2更新为原来的max1，再将max1设为当前元素。
   • 如果当前元素小于max1但大于max2，且不等于max1：更新max2为当前元素。
3. 对第二个数组执行同样的遍历更新逻辑。
4. 遍历结束后，判断max2的状态：
   • 若max2仍为负无穷，说明所有得分相同或只有一个有效得分，此时不存在严格意义上的第二高分（可根据需求返回最高分或提示）。

边界情况处理 #

• 其中一个数组为空：直接处理非空数组即可。
• 两个数组各只有一个元素：若得分相同则无第二高分；若不同，第二高分是较小的那个。
• 存在多个相同最高分：比如arr1=[90,90]、arr2=[85,80]，第二高分是85。
• 所有得分都相同：比如arr1=[30,30]、arr2=[30]，无第二高分。
• 得分包含0或负数：比如arr1=[-5,0]、arr2=[-10]，第二高分是-5。

代码示例（Python） #

def find_second_highest(arr1, arr2):
    max1 = max2 = float('-inf')
    
    # 处理第一个数组
    for num in arr1:
        if num > max1:
            max2 = max1
            max1 = num
        elif num > max2 and num != max1:
            max2 = num
    
    # 处理第二个数组
    for num in arr2:
        if num > max1:
            max2 = max1
            max1 = num
        elif num > max2 and num != max1:
            max2 = num
    
    # 处理无第二高分的场景
    if max2 == float('-inf'):
        return "无第二高分（所有得分相同或仅一个有效得分）"
    return max2

# 示例测试
arr1 = [25, 45, 43, 67, 82]
arr2 = [30, 18, 10, 90, 85]
print(find_second_highest(arr1, arr2))  # 输出：85

# 边界测试：多个相同最高分
arr3 = [90,90]
arr4 = [85,80]
print(find_second_highest(arr3, arr4))  # 输出：85

# 边界测试：所有得分相同
arr5 = [30,30]
arr6 = [30]
print(find_second_highest(arr5, arr6))  # 输出：无第二高分（所有得分相同或仅一个有效得分）

效率对比 #

排序法需要先合并两个数组再排序，时间复杂度为O((n+m)log(n+m))，且需要额外空间存储合并后的数组。而上述遍历法仅用两个变量，线性遍历一次即可完成，空间复杂度为O(1)，数据量越大，效率优势越明显。

内容的提问来源于stack exchange，提问作者Pranay Mahajan