Formatted question description: https://leetcode.ca/all/1090.html
1090. Largest Values From Labels (Medium)
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 inS
with labelL
is<= use_limit
.
Return the largest possible sum of the subset S
.
Example 1:
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted
= 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.
Example 2:
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted
= 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.
Example 3:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted
= 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.
Example 4:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted
= 3, use_limit = 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
Related Topics:
Hash Table, Greedy
Solution 1.
// OJ: https://leetcode.com/problems/largest-values-from-labels/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
int N = values.size();
vector<int> id(N);
iota(begin(id), end(id), 0);
sort(begin(id), end(id), [&](int a, int b) { return values[a] > values[b]; });
unordered_map<int, int> m;
int ans = 0;
for (int i = 0; i < N && num_wanted > 0; ++i) {
int j = id[i];
if (m[labels[j]] >= use_limit) continue;
ans += values[j];
m[labels[j]]++;
num_wanted--;
}
return ans;
}
};
Java
-
class Solution { public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) { int length = values.length; int[][] valuesLabels = new int[length][2]; for (int i = 0; i < length; i++) { valuesLabels[i][0] = values[i]; valuesLabels[i][1] = labels[i]; } Arrays.sort(valuesLabels, new Comparator<int[]>() { public int compare(int[] valueLabel1, int[] valueLabel2) { if (valueLabel1[0] != valueLabel2[0]) return valueLabel2[0] - valueLabel1[0]; else return valueLabel1[1] - valueLabel2[1]; } }); Map<Integer, Integer> labelCountMap = new HashMap<Integer, Integer>(); Set<Integer> labelsLimitSet = new HashSet<Integer>(); int sum = 0; int itemsCount = 0; int index = 0; while (index < length && itemsCount < num_wanted) { int[] valueLabel = valuesLabels[index++]; int value = valueLabel[0], label = valueLabel[1]; if (!labelsLimitSet.contains(label)) { int labelCount = labelCountMap.getOrDefault(label, 0); labelCount++; if (labelCount == use_limit) { labelCountMap.remove(label); labelsLimitSet.add(label); } else labelCountMap.put(label, labelCount); sum += value; itemsCount++; } } return sum; } }
-
// OJ: https://leetcode.com/problems/largest-values-from-labels/ // Time: O(NlogN) // Space: O(N) class Solution { public: int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) { int N = values.size(); vector<int> id(N); iota(begin(id), end(id), 0); sort(begin(id), end(id), [&](int a, int b) { return values[a] > values[b]; }); unordered_map<int, int> m; int ans = 0; for (int i = 0; i < N && num_wanted > 0; ++i) { int j = id[i]; if (m[labels[j]] >= use_limit) continue; ans += values[j]; m[labels[j]]++; num_wanted--; } return ans; } };
-
# 1090. Largest Values From Labels # https://leetcode.com/problems/largest-values-from-labels/ class Solution: def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int: labels = [i[1] for i in sorted(enumerate(labels), key = lambda x:(-values[x[0]]))] values.sort(reverse = True) used = collections.defaultdict(int) res = i = 0 while i < len(values) and num_wanted > 0: v, l = values[i], labels[i] if used[l] < use_limit: res += v used[l] += 1 num_wanted -= 1 i += 1 return res