2554. Maximum Number of Integers to Choose From a Range I

難度: Medium

類型: Array, Hash Table, Binary Search, Greedy, Sorting

C程式下載: 2554.c

前情題要:

最多正整數的和, 不含被 banned 的正整數, 正整數最大不超過 n, 總和不超過 maxSum。回傳最多個正整數的個數。

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

• The chosen integers have to be in the range [1, n].
• Each integer can be chosen at most once.
• The chosen integers should not be in the array banned.
• The sum of the chosen integers should not exceed maxSum.

Return the maximum number of integers you can choose following the mentioned rules.

 

Example 1:

Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation: You can choose the integers 2 and 4.
2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.

Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: You cannot choose any integer while following the mentioned conditions.

Example 3:

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7.
They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.

 

Constraints:

• 1 <= banned.length <= 104
• 1 <= banned[i], n <= 104
• 1 <= maxSum <= 109

思考方式:

1. 把ban掉的正整數記下來。

2. 從小到大開始相加, 被 banned 掉的數字不算, 加到最接近 maxSum 但不超過, 回傳相加的正整數個數。

複雜度思考:

Time Complexity: O( N+max(10^4) ) 

Space Complexity: O( 10001 * sizeof(int))

Runtime: 0 ms, Beats: 100%

Memory: 15.06 MB, Beats: 73.08%

Accepted

208 / 208 testcases passed

tendchen

submitted at Jun 12, 2025 19:56

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

15.06MB

Beats73.08%

Analyze Complexity

Code

C

int maxCount(int* banned, int bannedSize, int n, int maxSum) {
    int i,j;
    int cur_sum=0, num=0;
    //int max_num=0;
    bool bBanned[10001];
    //printf("sizeof bBanned=%d",sizeof(bBanned));
    memset(bBanned,0,sizeof(bBanned));
    for (j=0;j<bannedSize;j++)
    {
        bBanned[banned[j]]=1;
    }

    for (i=1;i<=n;i++)
    {
        if (bBanned[i]==0)
        {
            cur_sum=cur_sum+i;
            if (cur_sum<=maxSum)
            {
                //max_num=i;
                num++;
                
            }
            else
            {
                break;
            }
        }
    }
    return num;
}