2025-09-03：找出最大的几近缺失整数。用go语言，给定一个整数数组 nums 和一个正整数 k。把某个整数 x 视为“几

福大大架构师每日一题

发布于 2025-12-18 11:14:11

340

2025-09-03：找出最大的几近缺失整数。用go语言，给定一个整数数组 nums 和一个正整数 k。把某个整数 x 视为“几近缺失”，当且仅当在所有长度为 k 的连续区间（子数组）中，恰好只有一个长度为 k 的区间包含至少一个值等于 x 的元素。要求找出所有满足该条件的 x 中的最大值，若没有这样的数则返回 -1。这里的“子数组”指数组中一段连续的元素序列。

1 <= nums.length <= 50。

0 <= nums[i] <= 50。

1 <= k <= nums.length。

输入：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 ，因为它满足题意的所有整数中最大的那个。

题目来自力扣3471。

解决思路

1. 理解条件：对于某个整数 x，在所有长度为 k 的连续子数组中，有且仅有一个子数组包含 x（即 x 只出现在一个滑动窗口中）。注意，同一个子数组中可能出现多次 x，但只要该子数组包含 x，就算作一次出现。
2. 关键观察：
- • 如果 x 在整个数组中出现多次，那么它可能出现在多个滑动窗口中，因此不满足条件（除非这些出现都集中在同一个滑动窗口？但注意条件：恰好只有一个滑动窗口包含 x，而不是出现次数为1）。
- • 实际上，条件要求：所有包含 x 的滑动窗口必须恰好是同一个（即只有一个窗口包含 x），而不是 x 只出现一次（因为同一个窗口内出现多次仍然只算一个窗口包含它）。
3. 直接方法：
- • 枚举所有可能的 x（因为 nums[i] 范围是 [0,50]，所以最多51个候选）。
- • 对于每个候选 x，检查它是否在数组中出现（如果根本没出现，显然不符合）。
- • 然后找出所有包含 x 的滑动窗口（即所有起始位置 i 使得子数组 nums[i:i+k] 中包含 x）。
- • 如果包含 x 的滑动窗口恰好只有一个，那么 x 是候选。
- • 最后取所有候选中的最大值。
4. 优化观察：
- • 注意：如果 x 出现在多个位置，那么这些位置必须非常接近，以至于所有出现都落在同一个滑动窗口内？但实际上，如果多个出现分散在不同窗口，那么包含 x 的窗口就不止一个。
- • 实际上，x 必须只出现在一个滑动窗口内（即所有出现位置必须被某个长度为 k 的窗口完全覆盖），并且其他任何窗口都不能包含 x。
- • 更具体地：设 x 的所有出现位置为索引集合 S。那么必须存在一个滑动窗口 [i, i+k-1] 使得 S 是它的子集（即所有出现都在该窗口内），并且对于任何其他窗口，都不包含 x（即其他窗口都不包含 S 中的任何索引）。
- • 但注意：如果 x 只出现一次（比如位置 p），那么包含 p 的滑动窗口有多个（只要窗口覆盖 p）？实际上，窗口起始位置 i 满足 max(0, p-k+1) <= i <= min(p, n-k)。所以只有当 p 非常靠近边界时，可能只有一个窗口包含它？
- • 例如：数组长度为 n，滑动窗口长度为k，一个位置p被多少个窗口覆盖？窗口起始位置i的范围是[max(0, p-k+1), min(p, n-k)]（实际上应该是i从0到n-k，且窗口[i, i+k-1]包含p当且仅当i <= p <= i+k-1，即i >= p - k + 1且i <= p）。所以包含单个位置p的窗口个数为min(p, n-k) - max(0, p-k+1) + 1。
- • 因此，只有当这个值等于1时，x（只出现一次）才满足条件。类似地，如果出现多次，必须所有出现都被同一个窗口覆盖，且其他窗口都不包含它们。
5. 另一种思路（与代码相关）：
- • 代码中提供了另一种方法（但似乎不完整？）： if k == n: 返回整个数组的最大值（因为只有一个窗口，所以所有元素都满足条件？但注意条件：恰好一个窗口包含x，而这里只有一个窗口，所以每个元素都满足？但要求是“至少一个x”，所以每个元素都出现一次（或多次）在这个窗口里，因此每个元素都满足条件？所以取最大值）。 if k == 1: 那么每个窗口就是一个元素。要求恰好一个窗口包含x（即x只出现一次？因为如果出现多次，那么多个窗口（每个窗口是一个元素）都会包含x）。所以统计出现次数为1的元素，取最大值。
- • 对于一般情况，代码尝试： return max(f(nums[1:], nums[0]), f(nums[:n-1], nums[n-1])) 其中 f(a, x) 检查x是否在切片a中出现，如果出现返回-1，否则返回x。
- • 这实际上是在检查第一个元素和最后一个元素是否满足条件？因为代码认为只有边界元素可能满足（但这是不正确的，例如示例中7是最后一个元素，确实满足；但中间元素也可能满足？例如数组[1,2,3,4]且k=2，那么2和3也可能满足？但这里代码只检查了首尾）。
- • 实际上，代码的解法是错误的（因为它只检查了首尾两个元素），但示例中恰好最后一个元素7满足。
- • 因此，我们需要正确的暴力方法。

详细步骤（正确暴力方法）

1. 初始化候选答案 ans = -1。
2. 枚举所有可能的整数 x（从0到50，因为nums[i]范围0~50），但也可以只枚举实际出现在数组中的数（但可能未出现的数不需要考虑，因为条件要求至少出现一次？实际上，如果x没出现，那么包含x的窗口数为0，不符合“恰好一个”的条件）。
3. 对于每个候选 x：
- • 如果 x 不在数组 nums 中出现，跳过。
- • 否则，找出所有包含 x 的滑动窗口（即所有起始索引 i（0<=i<=n-k）使得子数组 nums[i:i+k] 中包含至少一个 x）。
- • 具体方法：对于每个起始位置 i，检查窗口 [i, i+k-1] 中是否存在值等于 x 的元素（只要有一个就够）。
- • 统计包含 x 的窗口个数，记为 count。
- • 如果 count == 1，那么 x 是满足条件的候选，更新 ans = max(ans, x)。
4. 返回 ans。

时间复杂度

• 枚举候选 x：最多51次（0到50）。
• 对于每个 x，需要检查所有滑动窗口（共 n-k+1 个窗口），每个窗口需要检查 k 个元素（最坏情况）。
• 因此总时间复杂度为 O(51 * (n-k+1) * k) = O(51 * n * k)。
• 由于 n <= 50, k <= n，所以最坏情况下 51 * 50 * 50 = 127500，非常小。

额外空间复杂度

• 只需要常数空间（几个变量），因此是 O(1)。

为什么示例中7满足？

• nums = [3,9,2,1,7], k=3。
• 滑动窗口有3个：[0:2] = [3,9,2], [1:3] = [9,2,1], [2:4] = [2,1,7]。
• 对于x=7：只出现在最后一个窗口[2,1,7]中（其他窗口都不包含7），所以包含7的窗口个数为1，因此满足条件。

总结

使用暴力方法枚举每个候选数字（0到50），对于每个数字统计包含它的滑动窗口数量（恰好为1则候选），然后取最大值。由于数据范围小，暴力可行。

总时间复杂度：O(51 * n * k) = O(127500) 最坏情况。 总额外空间复杂度：O(1)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func largestInteger(nums []int, k int)int {
    n := len(nums)
    if k == n {
        return slices.Max(nums)
    }
    if k == 1 {
        cnt := map[int]int{}
        for _, x := range nums {
            cnt[x]++
        }
        ans := -1
        for x, c := range cnt {
            if c == 1 {
                ans = max(ans, x)
            }
        }
        return ans
    }
    // nums[0] 不能出现在其他地方，nums[n-1] 同理
    return max(f(nums[1:], nums[0]), f(nums[:n-1], nums[n-1]))
}

func f(a []int, x int)int {
    if slices.Contains(a, x) {
        return-1
    }
    return x
}

func main() {
    nums := []int{3, 9, 2, 1, 7}
    k := 3
    result := largestInteger(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def largestInteger(nums, k):
    n = len(nums)
    if k == n:
        return max(nums)
    if k == 1:
        cnt = {}
        for x in nums:
            cnt[x] = cnt.get(x, 0) + 1
        ans = -1
        for x, c in cnt.items():
            if c == 1:
                ans = max(ans, x)
        return ans
    # nums[0] 不能出现在其他地方，nums[n-1] 同理
    return max(f(nums[1:], nums[0]), f(nums[:-1], nums[-1]))


def f(a, x):
    if x in a:
        return-1
    return x


if __name__ == "__main__":
    nums = [3, 9, 2, 1, 7]
    k = 3
    result = largestInteger(nums, k)
    print(result)