2. Linux.do
  3. Leetcode每日一题 —— 2996. 大于等于顺序前缀和的最小缺失整数

Leetcode每日一题 —— 2996. 大于等于顺序前缀和的最小缺失整数

魔法师 2026-08-11 09:02 1


思路


按题目模拟即可。


代码


class Solution {

    public int missingInteger(int[] nums) {

        int n = nums.length;

        int sum = nums[0];

        int idx = 1;

        for (; idx < n; idx++) {

            if (nums[idx] != nums[idx - 1] + 1) {

                break;

            }

            sum += nums[idx];

        }

        if (sum > 50) {

            return sum;

        }

        Arrays.sort(nums);

        for (--idx; idx < n; idx++) {

            if (nums[idx] == sum) {

                sum++;

            }

            if (nums[idx] > sum) {

                return sum;

            }

        }

        return sum;

    }

}

PS


看耗时，4ms 19.05%。最快算法1ms，是什么算法这么快呢？是朴素的把和每次循环一遍。所以如果数据量小就别想多了 ^-^

最新回复 (6)
  • SomeBottle 08-11 09:08
    1楼

    模拟 + 哈希表。看清楚题，注意是找的前缀。咱最开始做成找符合要求的连续子序列了…


    class Solution {
    
public:
    
    int missingInteger(vector<int>& nums) {
    
        // 先找到**最长**顺序前缀并求和
    
        // 看清楚题了，说的是**前缀**而不是连续子序列
    
        int sqSum=nums[0];
    
        bool confirmed=false;
    
        bool ap[51]; // 标记每个数字是否出现过
    
        memset(ap,0,51);
    
        ap[nums[0]]=true;
    
        for(int i=1;i<nums.size();i++){
    
            ap[nums[i]]=true;
    
            if(!confirmed&&nums[i]-nums[i-1]==1){
    
                // 是顺序的
    
                sqSum+=nums[i];
    
            }else{
    
                confirmed=true;
    
            }
    
        }
    
        while(sqSum<=50&&ap[sqSum]){
    
            sqSum++;
    
        }
    
        return sqSum;
    
    }
    
};
  • Infinity4B 08-11 09:31
    2楼

    算术评级 3 第 121 场双周赛 Q1 难度分 1406


    纯弱智题来的


    class Solution:
    
    def missingInteger(self, nums: List[int]) -> int:
    
        n=len(nums)
    
        cur_row=1
    
        cur_sum=nums[0]
    
        for i in range(1,n):
    
            if i and nums[i]==nums[i-1]+1:
    
                cur_row+=1
    
                cur_sum+=nums[i]
    
            else:
    
                break
    
        nums_set = set(nums)
    
        while cur_sum in nums_set:
    
            cur_sum+=1
    
        return cur_sum
  • doge 08-11 10:38
    3楼

    大力出奇迹


    class Solution:
    
    def missingInteger(self, nums: List[int]) -> int:
    
        n = len(nums)
    
        tot = nums[0]
    
        for i in range(1, n):
    
            if nums[i] == nums[i - 1] + 1:
    
                tot += nums[i]
    
            else:
    
                break
    
        
    
        cnt = Counter(nums)
    
        ans = tot
    
        while ans in cnt:
    
            ans += 1
    
        return ans
  • Lvvvv 08-11 11:29
    4楼

    丑陋了


    class Solution {
    
public:
    
    int missingInteger(vector<int>& nums) {
    
        int sum = nums[0];
    
        int n = nums.size();
    
        const int N = 50;
    
        vector<int> st(N + 1,false);
    
        st[nums[0]] = true;
    
        for(int i = 1; i < n; i++) {
    
            if(nums[i] == nums[i - 1] + 1) {
    
                sum += nums[i];
    
                st[nums[i]] = true;
    
            } else {
    
                while(i < n) {
    
                    st[nums[i]] = true;
    
                    i++;
    
                }
    
                while(sum <= N) {
    
                    if(st[sum]) {
    
                        sum++;
    
                    } else {
    
                        break;
    
                    }
    
                }
    
                return sum;
    
            }
    
        }
    
        if(n == 1) {
    
            return nums[0] + 1;
    
        } else {
    
            return sum;
    
        }
    
        
    
    }
    
};
  • CPython 08-11 11:49
    5楼 
    class Solution:
    
    def missingInteger(self, nums: List[int]) -> int:
    
        st = set(nums)
    
        n = len(nums)
    
        pre = cur = nums[0]
    
        for i in range(1, n):
    
            if nums[i] - 1 == pre:
    
                cur += nums[i]
    
                pre = nums[i]
    
            else:
    
                break
    
        while cur in st:
    
            cur += 1
    
        return cur

    丢了一个break刚开始

  • attention1111 08-11 11:50
    6楼

    简单题


    class Solution:
    
    def missingInteger(self, nums: List[int]) -> int:
    
        pre=nums[0]-1
    
        nums_sum=0
    
        find=set(nums)
    
        for i in range(0,len(nums)):
    
            if nums[i]==pre+1:
    
                nums_sum+=nums[i]
    
                pre=nums[i]
    
            else: break
    
        while(nums_sum in find):
    
            nums_sum+=1
    
        return nums_sum
* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐