LeetCode -- 1833. 雪糕的最大数量

使用的算法

• 计数排序 + 贪心算法
• 计数排序 ：
• 1 基于比较的排序算法
• 2 在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。
• （当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n))）

/**
 * 1833. 雪糕的最大数量
 *
 * 计数排序 + 贪心算法
 * 计数排序 ：
 * 1 基于比较的排序算法
 * 2 在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。
 * （当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n))）
 * 贪心：每次都是只选择最便宜的（买最便宜的可以花费的钱少，买的多）
 */

public class Solution1833 {
  public int maxIceCream(int[] costs, int coins) {
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    for (int cost : costs) {
      if (max < cost) {
        max = cost;
      }
      if (min > cost) {
        min = cost;
      }
    }
    int len = max - min + 1;
    int[] freq = new int[len];
    for (int cost : costs) {
      freq[cost - min]++;
    }
    int count = 0;
    for (int i = 0; i < len; i++) {
      if (coins >= i) {
        int curCount = Math.min(freq[i], coins / (i + min));
        count += curCount;
        coins -= (i + min) * curCount;
      } else {
        break;
      }
    }
    return count;
  }
}