Leetcode每日一题 —— 3471. 找出最大的几近缺失整数

魔法师 2026-08-18 09:06 1

思路

分类讨论

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);

    }

}

最新回复 (2)

SomeBottle 08-18 09:27

1楼

分类讨论题。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;

    }

};

Lvvvv 08-18 12:10

2楼

蛮力能做

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;

    }

};

* 帖子来源Linux.do

附近帖子