- 魔法师2026-08-18
力扣 LeetCode
3471. 找出最大的几近缺失整数 - 力扣（LeetCode）
3471. 找出最大的几近缺失整数 - 给你一个整数数组 nums 和一个整数 k 。
如果整数 x 恰好仅出现在 nums 中的一个大小为 k 的子数组中，则认为 x 是 nums 中的几近缺失（almost missing）整数。
返回 nums 中 最大的几近缺失 整数，如果不存在这样的整数，返回 -1 。
子数组 是数组中的一个连续元素序列。
示例 1：
输入：nums = [3,9,2,1,7], k = 3
输出：7
解释：
* 1 出现在两个大小为 3...
思路
分类讨论
- k==n 所有元素都 只在1个子数组中出现过，直接取最大的。
- k==1 所有元素独立1个子数组，所以取 只出现过1次的数值 中最大的。
- 排除了1、2后，只有**头元素和尾元素可能只出现过1次**。分以下两种情况
- nums[0]==nums[n-1] ，没有元素只出现过1次，返回-1。
- 遍历所有元素，检查是否存在与头、尾元素相等的元素，如果有从可能性中排除。如果头、尾的可能性都存在，取最大那个；如果只有一个，直接返回这个元素；如果都被排除，返回-1.
代码```
class Solution {
public int largestInteger(int[] nums, int k) {
int n = nums.length;
if (k == n) {
int max = 0;
for (int num : nums) {
max = Math.max(max, num);
}
return max;
}
if (k == 1) {
int[] cnt = new int[51];
for (int num : nums) {
cnt[num]++;
}
for (int i = 50; i > 0; i--) {
if (cnt[i] == 1) {
return i;
}
}
}
int s = nums[0], e = nums[n - 1];
if (s == e) {
return -1;
}
for (int i = 1; i < n - 1; i++) {
if (nums[i] == s) {
s = -1;
}
if (nums[i] == e) {
e = -1;
}
}
return Math.max(s, e);
}
}主楼 - SomeBottle2026-08-18
分类讨论题。
k=1时找不重复出现的最大数字，k=len(nums)时找最大数字，其余情况只用关注首尾两个数字。```
class Solution {
public:
int largestInteger(vector<int>& nums, int k) {
// 滑动大小为 k 的窗口
// 要找到在滑动过程中只出现过一次的整数// 如果 k=nums.size()，就是找最大数字
if(k==nums.size()){
int maxVal=0;
for(int num:nums){
maxVal=max(maxVal,num);
}
return maxVal;
}
// 如果 k=1，则找不重复的最大数字
if(k==1){
int nMap[51];
memset(nMap,0,sizeof(nMap));
for(int num:nums){
nMap[num]++;
}
int res=-1;
for(int num=0;num<=50;num++){
if(nMap[num]==1){
res=max(res,num);
}
}
return res;
}
// 其余只需要关注首尾两个数的出现情况
bool first=true;
bool second=true;
if(nums[0]==nums[nums.size()-1]){
// 首尾数字相同，除非 k=len(nums)，否则不存在符合要求的
return -1;
}
int res=-1;
for(int i=1;i<nums.size()-1;i++){
if(nums[i]==nums[0]){
// 首个数再次出现了
first=false;
}else if(nums[i]==nums[nums.size()-1]){
// 最后一个数再次出现了
second=false;
}
}
if(first)
res=max(res,nums[0]);
if(second)
res=max(res,nums[nums.size()-1]);
return res;
}
}; - Lvvvv2026-08-18
蛮力能做```
class Solution {
public:
int largestInteger(vector<int>& nums, int k) {
int res = -1;
int n = nums.size();
const int N = 50;
vector<int> cnt(N + 1,0);
for(int i = 0; i + k - 1 < n; i++) {
int j = i;
vector<bool> st(N + 1, false);
while(j - i + 1 <= k) {
if(!st[nums[j]]) {
cnt[nums[j]]++;
}
st[nums[j]] = true;
j++;
}
}
for(int i = 0; i < N + 1; i++) {
if(cnt[i] == 1) {
res = max(res,i);
}
}
return res;
}
};