Question

1196. 最多可以买到的苹果数量

English Version

题目描述

你有一些苹果和一个可以承载 5000 单位重量的篮子。

给定一个整数数组 weight ，其中 weight[i] 是第 i 个苹果的重量，返回 _你可以放入篮子的最大苹果数量_ 。

 

示例 1：

输入：weight = [100,200,150,1000]
输出：4
解释：所有 4 个苹果都可以装进去，因为它们的重量之和为 1450。

示例 2：

输入：weight = [900,950,800,1000,700,800]
输出：5
解释：6 个苹果的总重量超过了 5000，所以我们只能从中任选 5 个。

 

提示：

• 1 <= weight.length <= 103
• 1 <= weight[i] <= 103

解法

方法一：贪心

要使得苹果数量最多，那么就要使得苹果的重量尽可能的小，因此我们可以对苹果的重量进行排序，然后从小到大依次放入篮子中，直到篮子的重量超过 $5000$ 为止，返回此时放入篮子的苹果数量。

如果所有的苹果都能放入篮子中，那么就返回苹果的数量。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是苹果的数量。

class Solution:
  def maxNumberOfApples(self, weight: List[int]) -> int:
    weight.sort()
    s = 0
    for i, x in enumerate(weight):
      s += x
      if s > 5000:
        return i
    return len(weight)

class Solution {
  public int maxNumberOfApples(int[] weight) {
    Arrays.sort(weight);
    int s = 0;
    for (int i = 0; i < weight.length; ++i) {
      s += weight[i];
      if (s > 5000) {
        return i;
      }
    }
    return weight.length;
  }
}

class Solution {
public:
  int maxNumberOfApples(vector<int>& weight) {
    sort(weight.begin(), weight.end());
    int s = 0;
    for (int i = 0; i < weight.size(); ++i) {
      s += weight[i];
      if (s > 5000) {
        return i;
      }
    }
    return weight.size();
  }
};

func maxNumberOfApples(weight []int) int {
  sort.Ints(weight)
  s := 0
  for i, x := range weight {
    s += x
    if s > 5000 {
      return i
    }
  }
  return len(weight)
}

function maxNumberOfApples(weight: number[]): number {
  weight.sort((a, b) => a - b);
  let s = 0;
  for (let i = 0; i < weight.length; ++i) {
    s += weight[i];
    if (s > 5000) {
      return i;
    }
  }
  return weight.length;
}