[Swift]LeetCode1090.受标签影响的最大值|LargestValuesFromLabels

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

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

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

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

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

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

We have a set of items: the i-th item has value values[i] and label labels[i].

Then, we choose a subset S of these items, such that:

|S| <= num_wanted
For every label L, the number of items in S with label L is <= use_limit.

Return the largest possible sum of the subset S.

Example 1:

Input: values = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.

Example 2:

Input: values = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.

Example 3:

Input: values = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.

Example 4:

Input: values = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.

Note:

1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length

我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。

我们从这些项中选出一个子集 S，这样一来：

|S| <= num_wanted
对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。

返回子集 S 的最大可能的和。

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。

示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。

示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出：16
解释：选出的子集是第一项和第四项。

示例 4：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出：24
解释：选出的子集是第一项，第二项和第四项。

提示：

1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length

188ms

 1 class Solution
 2 {
 3     struct LabelMap
 4     {
 5         let val: Int
 6         let label: Int
 7     }
 8     
 9     func largestValsFromLabels(_ values: [Int], _ labels: [Int], _ num_wanted: Int, _ use_limit: Int) -> Int
10     {
11         var data:[LabelMap] = []
12         var usedLabel: [Int: Int] = [:]
13         
14         // form data list
15         for i in 0..<values.count
16         {
17             let label = labels[i]
18             data.append(LabelMap(val: values[i], label: label))
19             
20             if let _ = usedLabel[label] {
21                 // do nothing
22             } else {
23                 usedLabel[label] = use_limit
24             }
25         }
26         
27         // sort by value
28         data.sort(by: { (a, b) in
29             return a.val > b.val
30         })
31         
32         // iterate
33         var sum = 0
34         var count = 0
35         for i in 0..<data.count
36         {
37             let d = data[i]
38             
39             let remindCount = usedLabel[d.label] ?? 0
40             if  remindCount > 0
41             {
42                 sum += d.val
43                 usedLabel[d.label] = remindCount - 1
44                 
45                 count += 1
46                 if count == num_wanted { break }
47             }
48         }
49         
50         return sum
51     }
52 }

192ms

 1 struct Info {
 2     var value: Int
 3     var label: Int
 4 }
 5 
 6 class Solution {
 7     func largestValsFromLabels(_ values: [Int], _ labels: [Int], _ num_wanted: Int, _ use_limit: Int) -> Int {
 8         let count = values.count
 9         var array = [Info]()
10         for index in 0..<count {
11             let info = Info(value: values[index], label: labels[index])
12             array.append(info)
13         }
14         array.sort { $0.value > $1.value }
15         var index = 0
16         var nums = 0
17         var sum = 0
18         var dict = [Int: Int]()
19         while index < count && nums < num_wanted {
20             let item = array[index]
21             if let uses = dict[item.label] {
22                 if uses + 1 > use_limit {
23                     index += 1
24                     continue
25                 } else {
26                     dict[item.label] = uses + 1
27                 }
28             } else {
29                 dict[item.label] = 1
30             }
31             sum += item.value
32             nums += 1
33             index += 1
34         }
35         return sum
36     }
37 }

200ms

 1 class Solution {
 2     struct Item {
 3         var value:Int
 4         var label:Int
 5         init(_ value:Int = 0, _ label: Int = 0) {
 6             self.value = value
 7             self.label = label
 8         }
 9     }
10     func largestValsFromLabels(_ values: [Int], _ labels: [Int], _ num_wanted: Int, _ use_limit: Int) -> Int {
11         var items = [Item]()
12         var dict = [Int: Int]()
13         for i in values.indices {
14             items.append(Item(values[i], labels[i]))
15             dict[labels[i], default: 0] = use_limit
16         }
17         items.sort(by: { $0.value > $1.value })
18         // print(items)
19         var count = num_wanted
20         var result = 0
21         for item in items {
22             if count > 0 && dict[item.label]! > 0 {
23                 result += item.value
24                 dict[item.label]! -= 1
25                 count -= 1
26             }
27             
28             if count == 0 {
29                 return result
30             }
31         }
32         return result
33     }
34 }

216ms

 1 class Solution {
 2     func largestValsFromLabels(_ values: [Int], _ labels: [Int], _ num_wanted: Int, _ use_limit: Int) -> Int {
 3         var pairs = (0..<values.count).map { (values[$0], labels[$0] ) }
 4         pairs.sort { $0.0 > $1.0 }
 5         var num_left = num_wanted
 6         var selected = [Int:Int]()
 7         var res = 0
 8         for (value, label) in pairs where num_left > 0 && (selected[label] ?? 0) < use_limit {
 9             selected[label] = (selected[label] ?? 0) + 1
10             res += value
11             num_left -= 1
12         }
13         return res
14     }
15 }

228ms

 1 class Solution {
 2     func largestValsFromLabels(_ values: [Int], _ labels: [Int], _ num_wanted: Int, _ use_limit: Int) -> Int {
 3     let zipped = zip(values, labels).sorted{a,b in
 4         return a.0 > b.0
 5     }    
 6     var used: [Int: Int] = [:] // label: times
 7     var idx = 0
 8     var numChosen = 0
 9     var sum = 0
10     while idx < values.count {
11         if used[zipped[idx].1, default: 0] < use_limit {
12             used[zipped[idx].1, default: 0] += 1
13             sum += zipped[idx].0
14             numChosen += 1
15             if numChosen == num_wanted {
16                 return sum
17             }
18         }
19         
20         idx += 1
21     }
22     
23     return sum
24     }
25 }

Runtime: 236 ms

Memory Usage: 21.6 MB

 1 class Solution {
 2     func largestValsFromLabels(_ values: [Int], _ labels: [Int], _ num_wanted: Int, _ use_limit: Int) -> Int {
 3         var labels = labels
 4         var num_wanted = num_wanted
 5         var v:[[Int]] = [[Int]]()
 6         for i in 0..<values.count
 7         {
 8             v.append([values[i], labels[i]])
 9         }
10         v = v.sorted(by:{
11             if $0[0] == $1[0]
12             {
13                 return $0[1] >= $1[1]
14             }
15             else
16             {
17                 return $0[0] >= $1[0]
18             }
19         })
20         
21         var ret:Int = 0
22         var f:[Int] = [Int](repeating:0,count:20002)
23         for i in 0..<v.count
24         {
25             if num_wanted == 0 {break}
26             if f[v[i][1]] < use_limit
27             {
28                 f[v[i][1]] += 1
29                 num_wanted -= 1
30                 ret += v[i][0]
31             }
32         }
33         return ret
34     }
35 }