2025-09-07:水果成篮Ⅱ。用go语言,给定两个长度为 n 的整型数组 fruits 和 baskets,前者 fruit
2025-09-07:水果成篮Ⅱ。用go语言,给定两个长度为 n 的整型数组 fruits 和 baskets,前者 fruits[i] 表示第 i 类水果的数量,后者 baskets[j] 表示第 j 个篮子的容量上限。
按以下步骤将水果依序放入篮子:
-
按 fruits 索引从小到大逐一处理每一类水果;
-
对于当前这类水果,要放入从左到右第一个尚未被占用且容量至少等于该类数量的篮子;
-
每个篮子只能被一种水果占用,一旦占用就不能再用;
-
若找不到满足条件的篮子,则该类水果保持未放置状态。
最终返回完成上述过程后,仍未被放入任何篮子的水果种类数量。
n == fruits.length == baskets.length。
1 <= n <= 100。
1 <= fruits[i], baskets[i] <= 1000。
输入: fruits = [4,2,5], baskets = [3,5,4]。
输出: 1。
解释:
fruits[0] = 4 放入 baskets[1] = 5。
fruits[1] = 2 放入 baskets[0] = 3。
fruits[2] = 5 无法放入 baskets[2] = 4。
由于有一种水果未放置,我们返回 1。
题目来自力扣3477。
步骤描述:
-
初始化:
- 我们有一个水果数组
fruits
,其中每个元素fruits[i]
表示第i
类水果的数量。 - 我们有一个篮子数组
baskets
,其中每个元素baskets[j]
表示第j
个篮子的容量上限。 - 我们需要按索引从小到大(即从
fruits[0]
到fruits[n-1]
)逐一处理每一类水果。
- 我们有一个水果数组
-
处理每一类水果:
- 对于当前正在处理的水果
fruit
(即fruits[i]
),我们需要找到一个篮子来放置它。 - 查找篮子的规则是:从左到右(即从
baskets[0]
到baskets[n-1]
)扫描篮子数组,寻找第一个尚未被占用(即篮子容量值未被置零)且容量至少等于当前水果数量(即baskets[j] >= fruit
)的篮子。 - 如果找到这样的篮子:
- 将该篮子的容量置为零(标记为已被占用,防止后续水果再次使用)。
- 标记当前水果已被放置(即
unset
为0),并继续处理下一个水果。
- 如果找不到这样的篮子(即扫描完所有篮子都没有满足条件的):
- 当前水果无法被放置,计数
count
增加1(因为unset
保持为1)。
- 当前水果无法被放置,计数
- 对于当前正在处理的水果
-
重复处理:
- 对每一类水果重复上述过程,直到所有水果都被处理完毕。
-
返回结果:
- 最终返回
count
,即未被放入任何篮子的水果种类数量。
- 最终返回
具体例子(输入:fruits = [4,2,5], baskets = [3,5,4]):
- 处理第一类水果(4):
- 从左扫描篮子:第一个篮子容量为3(3<4,不满足),第二个篮子容量为5(5>=4,满足且未被占用)-> 占用第二个篮子(将其置0),此时baskets变为[3,0,4]。
- 处理第二类水果(2):
- 从左扫描篮子:第一个篮子容量为3(3>=2,满足且未被占用)-> 占用第一个篮子(将其置0),此时baskets变为[0,0,4]。
- 处理第三类水果(5):
- 从左扫描篮子:第一个篮子已被占用(值为0),第二个篮子已被占用(值为0),第三个篮子容量为4(4<5,不满足)-> 找不到可用篮子,计数增加1。
- 返回计数1。
复杂度分析:
-
时间复杂度:
对于每个水果(共n个),我们最坏情况下需要遍历整个篮子数组(长度n)来寻找可用的篮子。因此,总的时间复杂度为 O(n²)。 -
额外空间复杂度:
我们只使用了常数个额外变量(如count
、unset
和循环变量),没有使用与输入规模相关的额外数据结构。因此,总的额外空间复杂度为 O(1)。
注意:虽然我们修改了原始的baskets
数组(原地标记占用),但题目允许修改(根据代码逻辑),且这并不算额外空间(因为输入数组本身可被修改)。所以额外空间复杂度是常数。
Go完整代码如下:
package main
import (
"fmt"
)
func numOfUnplacedFruits(fruits []int, baskets []int) int {
count := 0
n := len(baskets)
for _, fruit := range fruits {
unset := 1
for i := 0; i < n; i++ {
if fruit <= baskets[i] {
baskets[i] = 0
unset = 0
break
}
}
count += unset
}
return count
}
func main() {
fruits := []int{4, 2, 5}
baskets := []int{3, 5, 4}
result := numOfUnplacedFruits(fruits, baskets)
fmt.Println(result)
}
Python完整代码如下:
# -*-coding:utf-8-*-
def num_of_unplaced_fruits(fruits, baskets):
count = 0
n = len(baskets)
for fruit in fruits:
unset = 1
for i in range(n):
if fruit <= baskets[i]:
baskets[i] = 0
unset = 0
break
count += unset
return count
if __name__ == "__main__":
fruits = [4, 2, 5]
baskets = [3, 5, 4]
result = num_of_unplaced_fruits(fruits, baskets)
print(result)
- 点赞
- 收藏
- 关注作者
评论(0)