Welcome to Subscribe On Youtube
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 inSwith labelLis<= 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 <= 200000 <= values[i], labels[i] <= 200001 <= num_wanted, use_limit <= values.length
Related Topics:
Hash Table, Greedy
Solution 1.
-
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; } } ############ class Solution { public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) { int n = values.length; int[][] p = new int[n][2]; for (int i = 0; i < n; ++i) { p[i] = new int[] {values[i], labels[i]}; } Arrays.sort(p, (a, b) -> b[0] - a[0]); int ans = 0; int num = 0; Map<Integer, Integer> counter = new HashMap<>(); for (int i = 0; i < n && num < numWanted; ++i) { int v = p[i][0], l = p[i][1]; if (counter.getOrDefault(l, 0) < useLimit) { counter.put(l, counter.getOrDefault(l, 0) + 1); ans += v; ++num; } } return ans; } } -
// 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; } }; -
class Solution: def largestValsFromLabels( self, values: List[int], labels: List[int], numWanted: int, useLimit: int ) -> int: arr = list(zip(values, labels)) arr.sort(reverse=True) cnt = Counter() ans = num = 0 for v, l in arr: if cnt[l] < useLimit: cnt[l] += 1 num += 1 ans += v if num == numWanted: break 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 -
func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int { var p [][]int for i, v := range values { p = append(p, []int{v, labels[i]}) } sort.Slice(p, func(i, j int) bool { return p[i][0] > p[j][0] }) counter := make(map[int]int) ans, num := 0, 0 for _, t := range p { if num >= numWanted { break } v, l := t[0], t[1] if counter[l] < useLimit { counter[l]++ num++ ans += v } } return ans } -
function largestValsFromLabels( values: number[], labels: number[], numWanted: number, useLimit: number, ): number { const n = values.length; const pairs = new Array(n); for (let i = 0; i < n; ++i) { pairs[i] = [values[i], labels[i]]; } pairs.sort((a, b) => b[0] - a[0]); const cnt: Map<number, number> = new Map(); let ans = 0; for (let i = 0, num = 0; i < n && num < numWanted; ++i) { const [v, l] = pairs[i]; if ((cnt.get(l) || 0) < useLimit) { cnt.set(l, (cnt.get(l) || 0) + 1); ++num; ans += v; } } return ans; }