2025-09-07:水果成篮Ⅱ。用go语言,给定两个长度为 n 的整型数组 fruits 和 baskets,前者 fruit

举报
福大大架构师每日一题 发表于 2025/09/07 08:54:38 2025/09/07
【摘要】 2025-09-07:水果成篮Ⅱ。用go语言,给定两个长度为 n 的整型数组 fruits 和 baskets,前者 fruits[i] 表示第 i 类水果的数量,后者 baskets[j] 表示第 j 个篮子的容量上限。按以下步骤将水果依序放入篮子:按 fruits 索引从小到大逐一处理每一类水果;对于当前这类水果,要放入从左到右第一个尚未被占用且容量至少等于该类数量的篮子;每个篮子只能被...

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。

步骤描述:

  1. 初始化

    • 我们有一个水果数组 fruits,其中每个元素 fruits[i] 表示第 i 类水果的数量。
    • 我们有一个篮子数组 baskets,其中每个元素 baskets[j] 表示第 j 个篮子的容量上限。
    • 我们需要按索引从小到大(即从 fruits[0]fruits[n-1])逐一处理每一类水果。
  2. 处理每一类水果

    • 对于当前正在处理的水果 fruit(即 fruits[i]),我们需要找到一个篮子来放置它。
    • 查找篮子的规则是:从左到右(即从 baskets[0]baskets[n-1])扫描篮子数组,寻找第一个尚未被占用(即篮子容量值未被置零)且容量至少等于当前水果数量(即 baskets[j] >= fruit)的篮子。
    • 如果找到这样的篮子:
      • 将该篮子的容量置为零(标记为已被占用,防止后续水果再次使用)。
      • 标记当前水果已被放置(即 unset 为0),并继续处理下一个水果。
    • 如果找不到这样的篮子(即扫描完所有篮子都没有满足条件的):
      • 当前水果无法被放置,计数 count 增加1(因为 unset 保持为1)。
  3. 重复处理

    • 对每一类水果重复上述过程,直到所有水果都被处理完毕。
  4. 返回结果

    • 最终返回 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²)

  • 额外空间复杂度
    我们只使用了常数个额外变量(如countunset和循环变量),没有使用与输入规模相关的额外数据结构。因此,总的额外空间复杂度为 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)

在这里插入图片描述

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。