【Leetcode 每日一题】1561. 你可以获得的最大硬币数目

问题背景

有 $3n$ 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：

• 每一轮中，你将会选出 任意 $3$ 堆硬币（不一定连续）。
• Alice 将会取走硬币数量最多的那一堆。
• 你将会取走硬币数量第二多的那一堆。
• Bob 将会取走最后一堆。
• 重复这个过程，直到没有更多硬币。
  给你一个整数数组 $piles$，其中 $piles[i]$ 是第 $i$ 堆中硬币的数目。
  返回你可以获得的最大硬币数目。

数据约束

• $3\le piles.length\le 10^5$
• $piles.length\%3=0$
• $1\le piles[i]\le 10^4$

解题过程

一个显而易见的方法，是排序之后从较大的三分之二元素中，跳着取值。
这题的数据范围不大，可以用 计数排序 或类似的思想将时间复杂度优化到 $O(N)$ 这个量级。

具体实现

调用 API

class Solution {
    public int maxCoins(int[] piles) {
        int n = piles.length;
        Arrays.sort(piles);
        int res = 0;
        for (int i = n / 3; i < n; i += 2) {
            res += piles[i];
        }
        return res;
    }
}

计数排序

class Solution {
    public int maxCoins(int[] piles) {
        int n = piles.length;
        countingSort(piles);
        int res = 0;
        for (int i = n / 3; i < n; i += 2) {
            res += piles[i];
        }
        return res;
    }

    private void countingSort(int[] nums) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int range = max - min + 1;
        int[] count = new int[range];
        for (int num : nums) {
            count[num - min]++;
        }
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }
        int[] res = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int cur = nums[i];
            res[--count[cur - min]] = cur;
        }
        System.arraycopy(res, 0, nums, 0, nums.length);
    }
}