[Swift]LeetCode781.森林中的兔子|RabbitsinForest

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10543038.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0

Note:

answers will have length at most 1000.
Each answers[i] will be an integer in the range [0, 999].

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]
输出: 11

输入: answers = []
输出: 0

说明:

answers 的长度最大为1000。
answers[i] 是在 [0, 999] 范围内的整数。

Runtime: 20 ms

Memory Usage: 19.3 MB

 1 class Solution {
 2     func numRabbits(_ answers: [Int]) -> Int {
 3         var res:Int = 0
 4         var m:[Int:Int] = [Int:Int]()
 5         for ans in answers
 6         {
 7             m[ans,default:0] += 1
 8         }
 9         for (key,val) in m
10         {
11             res += (val + key) / (key + 1) * (key + 1)
12         }
13         return res
14     }
15 }

24ms

 1 class Solution {
 2     func numRabbits(_ answers: [Int]) -> Int {
 3         var counter = [Int: Int]()
 4         answers.forEach{ counter[$0, default: 0] += 1 }
 5         
 6         var ret = 0
 7         for (n, c) in counter {
 8             let colors = (c + n) / (n + 1)
 9             ret += colors * (n + 1)
10         }
11         return ret
12     }
13 }

24ms

 1 class Solution {
 2     func numRabbits(_ answers: [Int]) -> Int {
 3         if answers.count == 0 {
 4         return 0
 5     }
 6     
 7     let sortAns = answers.sorted()
 8     var first = -1
 9 
10     var total = 0
11     var sep = 0
12     
13     for (_, itemCount) in sortAns.enumerated() {
14         if itemCount != first || sep == first {
15             first = itemCount
16             sep = 0
17             
18             total += 1 + itemCount
19         } else {
20             sep += 1
21         }
22     }
23     return total
24     }
25 }

48ms

 1 class Solution {
 2     func numRabbits(_ answers: [Int]) -> Int {
 3         var mark = [Int : Int]()
 4         for answer in answers {
 5             if let count = mark[answer] {
 6                 mark[answer] = count + 1
 7             } else {
 8                 mark[answer] = 1
 9             }
10         }
11         
12         var result = 0
13         for (key, value) in mark {
14             let groupNum = key + 1
15             var group = value / groupNum
16             if value % groupNum != 0 {
17                 group += 1
18             }
19             result += group * groupNum
20         }
21         return result
22     }
23 }