leetcode2226_go_每个小孩最多能分到多少糖果

wx_cyvef740

标题

给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies 的一堆糖果。
你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。
另给你一个整数 k 。你必要将这些糖果分配给 k 个小孩，使每个小孩分到 雷同 数量的糖果。
每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的 最大糖果数目 。
示例 1：输入：candies = [5,8,6], k = 3 输出：5
表明：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。
现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。
可以证明无法让每个小孩得到超过 5 颗糖果。
示例 2：输入：candies = [2,5], k = 11 输出：0
表明：总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。
因此，末了每个小孩都没有得到糖果，答案是 0 。
提示：1 <= candies.length <= 105
1 <= candies <= 107
1 <= k <= 1012
解题思路分析

1、二分查找；时间复杂度O(nlog(n))，空间复杂度O(1)

func maximumCandies(candies []int, k int64) int {   sum := int64(0)   maxValue := 0   for i := 0; i < len(candies); i++ {      sum = sum + int64(candies)      maxValue = max(maxValue, candies)   }   if sum < k {      return 0   }   left := 1   right := maxValue   for left <= right {      mid := left + (right-left)/2      total := check(candies, mid)      if total >= k {         left = mid + 1      } else {         right = mid - 1      }   }   return left - 1}func check(arr []int, target int) int64 {   res := int64(0)   for i := 0; i < len(arr); i++ {      res = res + int64(arr/target)   }   return res}func max(a, b int) int {   if a > b {      return a   }   return b}2、二分查找；时间复杂度O(nlog(n))，空间复杂度O(1)
func maximumCandies(candies []int, k int64) int {   sum := int64(0)   maxValue := 0   for i := 0; i < len(candies); i++ {      sum = sum + int64(candies)      maxValue = max(maxValue, candies)   }   if sum < k {      return 0   }   left := 1   right := maxValue + 1   for left < right {      mid := left + (right-left)/2      total := check(candies, mid)      if total >= k {         left = mid + 1      } else {         right = mid      }   }   return left - 1}func check(arr []int, target int) int64 {   res := int64(0)   for i := 0; i < len(arr); i++ {      res = res + int64(arr/target)   }   return res}func max(a, b int) int {   if a > b {      return a   }   return b}3、内置函数；时间复杂度O(nlog(n))，空间复杂度O(1)
func maximumCandies(candies []int, k int64) int {   sum := int64(0)   maxValue := 0   for i := 0; i < len(candies); i++ {      sum = sum + int64(candies)      maxValue = max(maxValue, candies)   }   if sum < k {      return 0   }   return sort.Search(maxValue+1, func(target int) bool {      if target == 0 {         return false      }      res := int64(0)      for i := 0; i < len(candies); i++ {         res = res + int64(candies/target)      }      return res < k   }) - 1}func max(a, b int) int {   if a > b {      return a   }   return b}总结

Medium标题，二分查找-最大化最小值、最小化最大值 模板标题

我说

leetcode2226_go_每个小孩最多能分到多少糖果

我说

转发了