在线时间:8:00-16:00
迪恩网络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 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 = [1, 1, 2] 输出: 5 解释: 两只回答了 "1" 的兔子可能有相同的颜色,设为红色。 之后回答了 "2" 的兔子不会是红色,否则他们的回答会相互矛盾。 设回答了 "2" 的兔子为蓝色。 此外,森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。 输入: answers = [10, 10, 10] 输出: 11 输入: answers = [] 输出: 0 说明:
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 }
|
请发表评论