3471.找出最大的几近缺失整数：三种情况判断

【LetMeFly】3471.找出最大的几近缺失整数：三种情况判断

力扣题目链接：https://leetcode.cn/problems/find-the-largest-almost-missing-integer/

给你一个整数数组 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 <= 50
• 0 <= nums[i] <= 50
• 1 <= k <= nums.length

解题方法：三种情况分类讨论

• 如果$n=k$，则真个数组只有一个子数组，返回数组最大值
• 如果$k=1$，则每个元素都是一个子数组，返回数组中出现次数为1的最大值
• 否则 $1\lt k\lt n$，则除了第一个数和最后一个数外，每个数都至少被包含到两个子数组中，必定不可能是最大的几近缺失整数。所以我们只需看首尾两数中有没有只出现一次的数，若有则返回大的那个

时空复杂度：

• 时间复杂度$O(n^2)$，其中$n=len(nums)$
• 空间复杂度$O(\log n)$，最大数据量是$50$不使用哈希表也很快

AC代码

C++

/*
 * @LastEditTime: 2026-08-18 16:46:31
 */
class Solution {
public:
    int largestInteger(vector<int>& nums, int k) {
        int n = nums.size();
        if (n == k) {
            return *max_element(nums.begin(), nums.end());
        }

        if (k == 1) {
            ranges::sort(nums);
            for (int i = n - 1; i >= 0; i--) {
                if (i - 1 >= 0 && nums[i - 1] == nums[i]) {
                    continue;
                }
                if (i + 1 < n && nums[i + 1] == nums[i]) {
                    continue;
                }
                return nums[i];
            }
            return -1;
        }
        
        int first = nums[0], last = nums.back();
        if (first == last) {
            return -1;
        }
        bool another1 = false, another2 = false;
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] == first) {
                another1 = true;
            }
            if (nums[i] == last) {
                another2 = true;
            }
        }
        if (another1 && another2) {
            return -1;
        }
        if (!another1 && !another2) {
            return max(first, last);
        }
        return another1 ? last : first;
    }
};

• 执行用时分布 0 ms 击败 100.00%
• 消耗内存分布 28.13 MB 击败 92.86%

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源