1090. 受标签影响的最大值 (opens new window)

解题思路：快排+哈希。最终子集的数量并不仅仅受到numWanted的约束，同时还要受到useLimit的约束。(如果数组所有的标签都是相同的，那么能够选择的数量受到useLimit限制)

先将数组从小到大排序，这里要注意排序后标签数组并不是连续的，因此从大到小遍历时，还需要用一个HashMap来记录每个标签的使用次数。

public static int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
    quicksort(values, labels, 0, values.length - 1);
    int ans=0;
    int j = values.length - 1;
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    while(numWanted>=0&&j>=0){
        Integer num = hashMap.getOrDefault(labels[j], 0);
        if(num<useLimit){
            ans += values[j];
            numWanted--;
            hashMap.put(labels[j], num + 1);
        }
        j--;
    }
    return ans;
}

private static void quicksort(int[] values, int[] labels, int low, int high) {
    if (low > high) {
        return;
    }
    int left=low,right=high;
    int base = values[low];
    while (low < high) {
        while (low<high&&values[high]>=base)high--;
        while (low<high&&values[low]<=base)low++;
        if (low < high) {
            int temp = values[high];
            values[high] = values[low];
            values[low] = temp;

            temp = labels[high];
            labels[high] = labels[low];
            labels[low] = temp;
        }
    }
    int temp = labels[low];
    labels[low] = labels[left];
    labels[left] = temp;

    values[left]=values[low];
    values[low] = base;
    quicksort(values, labels, left, low - 1);
    quicksort(values, labels, low + 1, right);
}