LeetCode 解題筆記：3471. Find the Largest Almost Missing Integer

作者：王一哲
日期：2026年8月18日


LeetCode 題目連結：3471. Find the Largest Almost Missing Integer

解題想法

簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，要從 $nums$ 之中找出長度為 $k$ 的連續子序列，子序列之中有一個數字只出現一次，回傳這些數字中的最大值。我一開始用的寫法非常直接，先找出所有長度為 $k$ 的連續子序列，將子序列存成 set，再將 set 存入 list 之中。接下來再依序從 $nums$ 讀取數字 $num$，檢查 $num$ 是否在所有的子序列中只出現一次而且 $num$ 大於目前的答案 $ans$，如果條件成立就更新 $ans$。這個寫法在 Python 的速度還可以，但是在 C++ 就很糟糕了。

比較好的寫法應該是列出以下 3 種狀況：

1. $k = n$，子序列就是 $nums$，回傳 $nums$ 之中的最大值。
2. $k = 1$，子序列就是 $nums$ 之中的每個數字，找出只在 $nums$ 之中出現一次的數字最大值。
3. $k \neq n, k \neq 1$，只需要找 $nums[0]$ 與 $nums[n-1]$，因為中間的數字至少會出現在 2 個子序列之中。答案有 4 種：
   1. $nums[0]$ 與 $nums[n-1]$ 都只出現一次，回傳較大者。
   2. $nums[0]$ 只出現一次，$nums[n-1]$ 出現 2 次以上，回傳 $nums[0]$。
   3. $nums[n-1]$ 只出現一次，$nums[0]$ 出現 2 次以上，回傳 $nums[n-1]$。
   4. 以上條件皆不成立，回傳 $-1$。

Python 程式碼

方法1，Runtime: 3 ms, beats 62.30%. Memory: 19.15 MB, beats 93.85%.

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)
        subs = [set() for _ in range(n-k+1)]
        for i in range(n-k+1):
            subs[i] = set(nums[i:i+k])

        ans = -1
        for num in nums:
            cnt = 0
            for sub in subs:
                if num in sub: cnt += 1
                if cnt >= 2: break
            if cnt == 1 and num > ans:
                ans = num
        return ans

方法2，Runtime: 1 ms, beats 70.90%. Memory: 19.36 MB, beats 35.66%.

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        # Case 1. k == n，回傳 nums 的最大值
        if k == n: return max(nums)

        # Case 2. k == 1，回傳只出現一次的數字最大值
        cnt = Counter(nums)  # 計數器
        if k == 1:
            ans = -1  # 答案預設為 -1
            for num in nums:
                if cnt[num] == 1 and num > ans:
                    ans = num
            return ans
        
        # Case 3. 一般狀況，只需要考慮 nums[0] 及 nums[n-1]，因為其它數字至少會出現在子序列之中 2 次
        first, last = nums[0], nums[-1]
        # first, last 次數都是 1，回傳較大者
        if cnt[first] == 1 and cnt[last] == 1:
            return max(first, last)
        # first 次數 1，last 次數大於 1，回傳 first
        if cnt[first] == 1 and cnt[last] > 1:
            return first
        # first 次數大於 1，last 次數 1，回傳 last
        if cnt[first] > 1 and cnt[last] == 1:
            return last
        # 沒有答案，回傳 -1
        return -1

C++ 程式碼

方法1，Runtime: 113 ms, beats 5.26%. Memory: 73.72 MB, beats 8.65%.

class Solution {
public:
    int largestInteger(vector<int>& nums, int k) {
        int n = (int)nums.size();
        vector<unordered_set<int>> subs (n-k+1);
        for(int i = 0; i <= n-k; i++) {
            unordered_set<int> curr (nums.begin() + i, nums.begin() + i + k);
            subs[i] = curr;
        }

        int ans = -1;
        for(int num : nums) {
            int cnt = 0;  // nums 於所有的 subarray 出現次數
            for(auto sub : subs) {
                if (sub.count(num) == 1) cnt++;
                if (cnt >= 2) break;
            }
            if (cnt == 1 && num > ans) ans = num;
        }
        return ans;
    }
};

方法2，Runtime: 0 ms, beats 100.00%. Memory: 29.13 MB, beats 73.68%.

class Solution {
public:
    int largestInteger(vector<int>& nums, int k) {
        int n = (int)nums.size(); // 長度
        
        /* Case 1: k == n，回傳 nums 之中的最大值 */
        if (k == n) {
            return *max_element(nums.begin(), nums.end());
        }
        
        /* Case 2: k == 1，回傳只出現一次的數字最大值 */
        int cnt[51] = {0};  // 數字 0 ~ 50 計數器
        for(int num : nums) cnt[num]++;
        if (k == 1) {
            int ans = -1;
            for(int num : nums) {
                if (cnt[num] == 1) {
                    ans = max(ans, num);
                }
            }
            if (ans > 0) return ans;
        }

        /* Case 3: 一般狀況，只需要考慮 nums[0] 及 nums[n-1]，
           因為其它的數字一次會出現在子序列之中至少 2 次 */
        int first = nums[0], last = nums[n-1];
        // 次數都是 1，回傳較大者
        if (cnt[first] == 1 && cnt[last] == 1) {
            return max(first, last);
        }
        // first 次數都是 1，回傳 first
        if (cnt[first] == 1 && cnt[last] > 1) {
            return first;
        }
        // last 次數都是 1，回傳 last
        if (cnt[first] > 1 && cnt[last] == 1) {
            return last;
        }
        // 以上條件皆不成立，回傳 -1
        return -1;
    }
};

C 語言程式碼

方法2，Runtime: 0 ms, beats 100.00%. Memory: 10.36 MB, beats 52.94%.

int largestInteger(int* nums, int numsSize, int k) {
    /* Case 1. k = n，回傳 nums 的最大值 */
    if (k == numsSize) {
        int ans = -1;
        for(int i = 0; i < numsSize; i++) {
            if (nums[i] > ans) ans = nums[i];
        }
        return ans;
    }

    /* Case 2. k = 1，回傳只出現一次的數字最大值 */
    int cnt[51] = {0};  // 數字 0 ~ 50 計數器
    for(int i = 0; i < numsSize; i++) {
        cnt[nums[i]]++;
    }

    if (k == 1) {
        int ans = -1;
        for(int i = 0; i < numsSize; i++) {
            if (cnt[nums[i]] == 1 && nums[i] > ans) {
                ans = nums[i];
            }
        }
        return ans;
    }

    /* Case 3. 一般狀況，只要檢查 nums[0] 及 nums[numsSize - 1] */
    int first = nums[0], last = nums[numsSize - 1];
    if (cnt[first] == 1 && cnt[last] == 1) {
        if (first > last) return first;
        return last;
    }
    if (cnt[first] == 1 && cnt[last] > 1) {
        return first;
    }
    if (cnt[first] > 1 && cnt[last] == 1) {
        return last;
    }
    return -1;
}