LeetCode 题解工作台
找出最大的几近缺失整数
给你一个整数数组 nums 和一个整数 k 。 如果整数 x 恰好仅出现在 nums 中的一个大小为 k 的子数组中，则认为 x 是 nums 中的几近缺失（ almost missing ）整数。 返回 nums 中 最大的几近缺失 整数，如果不存在这样的整数，返回 -1 。 子数组 是数组中的一…
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
如果 $k = 1$，那么数组中每个元素都构成一个大小为 的子数组，此时我们只需要统计数组中只出现一次的元素中的最大值即可。 如果 $k = n$，那么整个数组构成一个大小为 的子数组，此时我们只需要返回数组中的最大值即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums 和一个整数 k 。
如果整数 x 恰好仅出现在 nums 中的一个大小为 k 的子数组中，则认为 x 是 nums 中的几近缺失（almost missing）整数。
返回 nums 中 最大的几近缺失 整数，如果不存在这样的整数，返回 -1 。
示例 1：
输入：nums = [3,9,2,1,7], k = 3
输出：7
解释：
- 1 出现在两个大小为 3 的子数组中：
[9, 2, 1]、[2, 1, 7] - 2 出现在三个大小为 3 的子数组中：
[3, 9, 2]、[9, 2, 1]、[2, 1, 7] - 3 出现在一个大小为 3 的子数组中：
[3, 9, 2] - 7 出现在一个大小为 3 的子数组中：
[2, 1, 7] - 9 出现在两个大小为 3 的子数组中：
[3, 9, 2]、[9, 2, 1]
返回 7 ，因为它满足题意的所有整数中最大的那个。
示例 2：
输入：nums = [3,9,7,2,1,7], k = 4
输出：3
解释：
- 1 出现在两个大小为 4 的子数组中：
[9, 7, 2, 1]、[7, 2, 1, 7] - 2 出现在三个大小为 4 的子数组中：
[3, 9, 7, 2]、[9, 7, 2, 1]、[7, 2, 1, 7] - 3 出现在一个大小为 4 的子数组中：
[3, 9, 7, 2] - 7 出现在三个大小为 4 的子数组中：
[3, 9, 7, 2]、[9, 7, 2, 1]、[7, 2, 1, 7] - 9 出现在两个大小为 4 的子数组中：
[3, 9, 7, 2]、[9, 7, 2, 1]
返回 3 ，因为它满足题意的所有整数中最大的那个。
示例 3：
输入：nums = [0,0], k = 1
输出：-1
解释：
不存在满足题意的整数。
提示：
1 <= nums.length <= 500 <= nums[i] <= 501 <= k <= nums.length
解题思路
方法一：分情况讨论
如果 ，那么数组中每个元素都构成一个大小为 的子数组，此时我们只需要统计数组中只出现一次的元素中的最大值即可。
如果 ，那么整个数组构成一个大小为 的子数组，此时我们只需要返回数组中的最大值即可。
如果 ，只有 和 可能是几近缺失整数，如果它们在数组中的其他位置出现过，那么它们就不是几近缺失整数。因此我们只需要判断 和 是否在数组中的其他位置出现过即可，取其中的最大值返回。
如果不存在几近缺失整数，返回 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def largestInteger(self, nums: List[int], k: int) -> int:
def f(k: int) -> int:
for i, x in enumerate(nums):
if i != k and x == nums[k]:
return -1
return nums[k]
if k == 1:
cnt = Counter(nums)
return max((x for x, v in cnt.items() if v == 1), default=-1)
if k == len(nums):
return max(nums)
return max(f(0), f(len(nums) - 1))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the approach for tracking subarrays and integers, but generally, it involves iterating through the array and checking subarrays, making it O(n * k) in most cases. Space complexity is determined by the hash table, which can store up to n unique elements, making it O(n). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates a good understanding of array scanning and hash tables.
- question_mark
The candidate correctly handles edge cases, particularly when k = 1 or k = n.
- question_mark
The candidate suggests an efficient approach to find the largest integer, showcasing optimal use of data structures.
常见陷阱
外企场景- error
Not correctly handling edge cases where k = 1 or k = n.
- error
Overcomplicating the solution by using additional data structures or algorithms not needed for this problem.
- error
Failing to efficiently identify the largest almost missing integer due to an incorrect filtering process.
进阶变体
外企场景- arrow_right_alt
Implement a version that returns the smallest almost missing integer.
- arrow_right_alt
Extend the problem to allow for larger values of k beyond the constraints.
- arrow_right_alt
Modify the problem to find the integer that appears in exactly two subarrays of size k.