Easy

题目描述

给你一个整数数组 nums 和一个整数 k。

如果整数 x 在 nums 中恰好出现在一个大小为 k 的子数组中，那么称 x 是 nums 中几乎缺失的整数。

返回 nums 中最大的几乎缺失整数。如果不存在这样的整数，返回 -1。

子数组是数组中连续的元素序列。

示例 1：

输入：nums = [3,9,2,1,7], k = 3
输出：7
解释：
1 出现在 2 个大小为 3 的子数组中：[9, 2, 1] 和 [2, 1, 7]。
2 出现在 3 个大小为 3 的子数组中：[3, 9, 2], [9, 2, 1], [2, 1, 7]。
3 出现在 1 个大小为 3 的子数组中：[3, 9, 2]。
7 出现在 1 个大小为 3 的子数组中：[2, 1, 7]。
9 出现在 2 个大小为 3 的子数组中：[3, 9, 2] 和 [9, 2, 1]。
返回 7，因为它是恰好出现在一个大小为 k 的子数组中的最大整数。

示例 2：

输入：nums = [3,9,7,2,1,7], k = 4
输出：3

示例 3：

输入：nums = [0,0], k = 1
输出：-1

约束条件：

  • 1 <= nums.length <= 50
  • 0 <= nums[i] <= 50
  • 1 <= k <= nums.length

解题思路

这道题需要找到恰好出现在一个大小为 k 的子数组中的最大整数。我们可以按照提示分三种情况讨论：

情况分析

情况1：k = 1 当 k = 1 时，每个元素都是一个长度为 1 的子数组。我们需要找到在整个数组中恰好出现一次的最大元素。

情况2：k = n（数组长度） 当 k 等于数组长度时，只有一个大小为 k 的子数组（整个数组），所以每个元素都恰好出现在一个子数组中。返回数组中的最大元素即可。

情况3：1 < k < n 这是最有趣的情况。根据数学分析，除了数组的第一个元素 nums[0] 和最后一个元素 nums[n-1] 外，其他所有元素都会出现在多个长度为 k 的子数组中。

具体来说：

  • nums[0] 只出现在以索引 0 开始的子数组中
  • nums[n-1] 只出现在以索引 n-k 开始的子数组中
  • 中间的元素会出现在多个子数组中

因此，我们只需要检查 nums[0] 和 nums[n-1]：

  • 如果某个元素在整个数组中出现次数超过1次，则不符合条件
  • 在符合条件的元素中返回最大值

算法步骤

  1. 首先统计数组中每个元素的出现次数
  2. 根据 k 的值分情况处理
  3. 对于情况3，特别检查首尾元素的出现次数
  4. 返回符合条件的最大元素

代码实现

class Solution {
public:
    int largestInteger(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> count;
        
        // 统计每个元素的出现次数
        for (int num : nums) {
            count[num]++;
        }
        
        if (k == 1) {
            // 情况1: k = 1，找出现恰好一次的最大元素
            int result = -1;
            for (auto& p : count) {
                if (p.second == 1) {
                    result = max(result, p.first);
                }
            }
            return result;
        } else if (k == n) {
            // 情况2: k = n，返回最大元素
            return *max_element(nums.begin(), nums.end());
        } else {
            // 情况3: 1 < k < n，只有首尾元素可能符合条件
            int result = -1;
            
            // 检查第一个元素
            if (count[nums[0]] == 1) {
                result = max(result, nums[0]);
            }
            
            // 检查最后一个元素
            if (count[nums[n-1]] == 1) {
                result = max(result, nums[n-1]);
            }
            
            return result;
        }
    }
};

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = Counter(nums)
        
        if k == 1:
            # 情况1: k = 1，找出现恰好一次的最大元素
            result = -1
            for num, freq in count.items():
                if freq == 1:
                    result = max(result, num)
            return result
        elif k == n:
            # 情况2: k = n，返回最大元素
            return max(nums)
        else:
            # 情况3: 1 < k < n，只有首尾元素可能符合条件
            result = -1
            
            # 检查第一个元素
            if count[nums[0]] == 1:
                result = max(result, nums[0])
            
            # 检查最后一个元素
            if count[nums[n-1]] == 1:
                result = max(result, nums[n-1])
            
            return result

public class Solution {
    public int LargestInteger(int[] nums, int k) {
        int n = nums.Length;
        var count = new Dictionary<int, int>();
        
        // 统计每个元素的出现次数
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        if (k == 1) {
            // 情况1: k = 1，找出现恰好一次的最大元素
            int result = -1;
            foreach (var kvp in count) {
                if (kvp.Value == 1) {
                    result = Math.Max(result, kvp.Key);
                }
            }
            return result;
        } else if (k == n) {
            // 情况2: k = n，返回最大元素
            return nums.Max();
        } else {
            // 情况3: 1 < k < n，只有首尾元素可能符合条件
            int result = -1;
            
            // 检查第一个元素
            if (count[nums[0]] == 1) {
                result = Math.Max(result, nums[0]);
            }
            
            // 检查最后一个元素
            if (count[nums[n-1]] == 1) {
                result = Math.Max(result, nums[n-1]);
            }
            
            return result;
        }
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestInteger = function(nums, k) {
    const count = new Map();
    
    for (let i = 0; i <= nums.length - k; i++) {
        const subarray = nums.slice(i, i + k);
        for (const num of subarray) {
            count.set(num, (count.get(num) || 0) + 1);
        }
    }
    
    let largest = -1;
    for (const [num, freq] of count) {
        if (freq === 1) {
            largest = Math.max(largest, num);
        }
    }
    
    return largest === -1 ? -1 : largest;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组统计元素频次，其中 n 是数组长度
空间复杂度O(n)使用哈希表存储元素频次，最坏情况下存储 n 个不同元素

相关题目