1090. 受标签影响的最大值.md

1090. 受标签影响的最大值

• 排序 + 哈希表

type Label = number;
type Times = number;
type LabelAndValue = { label: number; value: number };

function largestValsFromLabels(values: number[], labels: number[], num_wanted: number, use_limit: number): number {

    const labelAndValues: Array<LabelAndValue> = values.map((value: number, index: number): LabelAndValue => {
        return {
            label: labels[index],
            value,
        };
    });

    labelAndValues.sort((a: LabelAndValue, b: LabelAndValue) => b.value - a.value);

    let sum: number = 0,
        count: number = 0,
        rightIndex: number = 0;

    const map: Map<Label, Times> = new Map<Label, Times>();

    while (count < num_wanted && rightIndex < labelAndValues.length) {
        const label: Label = labelAndValues[rightIndex].label;
        const times: Times = map.get(label) || 0;
        if (times < use_limit) {
            sum += labelAndValues[rightIndex].value;
            ++count;
            map.set(label, times + 1);
        }

        ++rightIndex;
    }

    return sum;
};