maximum-number-of-integers-to-choose-from-a-range-i

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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

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

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

Example 3:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= banned.length &lt;= 104</code></li>
	<li><code>1 &lt;= banned[i], n &lt;= 104</code></li>
	<li><code>1 &lt;= maxSum &lt;= 109</code></li>
</ul>

maxCount

Maximum Number of Integers to Choose From a Range I

First Missing Positive

first-missing-positive

缺失的第一个正数

Find All Numbers Disappeared in an Array

find-all-numbers-disappeared-in-an-array

找到所有数组中消失的数字

Append K Integers With Minimal Sum

append-k-integers-with-minimal-sum

向数组中追加 K 个整数

Replace Elements in an Array

replace-elements-in-an-array

替换数组中的元素

Maximum Number of Integers to Choose From a Range II

maximum-number-of-integers-to-choose-from-a-range-ii

从一个范围内选择最多整数 II

Greedy

Array

Hash Table

Binary Search

Sorting

给你一个整数数组&nbsp;<code>banned</code>&nbsp;和两个整数&nbsp;<code>n</code> 和&nbsp;<code>maxSum</code>&nbsp;。你需要按照以下规则选择一些整数：

<ul>
	<li>被选择整数的范围是&nbsp;<code>[1, n]</code>&nbsp;。</li>
	<li>每个整数 至多&nbsp;选择 一次&nbsp;。</li>
	<li>被选择整数不能在数组&nbsp;<code>banned</code>&nbsp;中。</li>
	<li>被选择整数的和不超过&nbsp;<code>maxSum</code>&nbsp;。</li>
</ul>

请你返回按照上述规则 最多&nbsp;可以选择的整数数目。

&nbsp;

示例 1：

<pre>输入：banned = [1,6,5], n = 5, maxSum = 6
输出：2
解释：你可以选择整数 2 和 4 。
2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。
</pre>

示例 2：

<pre>输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
输出：0
解释：按照上述规则无法选择任何整数。
</pre>

示例 3：

<pre>输入：banned = [11], n = 7, maxSum = 50
输出：7
解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。
它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= banned.length &lt;= 104</code></li>
	<li><code>1 &lt;= banned[i], n &lt;= 104</code></li>
	<li><code>1 &lt;= maxSum &lt;= 109</code></li>
</ul>