java - 俄罗斯娃娃 - 找到剩下的最少个娃娃

Question

我有N dolls各种尺寸。

我可以将较小的娃娃放在较大的娃娃里面，但尺寸完全相同的娃娃不能放在彼此里面。

我必须找到在包装完最大数量的娃娃后剩下的最少数量的娃娃。

Constraints
1≤N≤ 10⁵
1 ≤ size of doll ≤ 10⁵

Output Print the minimum number of dolls after placing all smaller dolls inside the larger dolls.

Example #1

Input 2, 2, 3, 3
Output 2

Explanation:

• Put the doll at index 1 inside the doll at index 3 i.e. the doll of size two into the doll size three.
• Put a doll at index 2 inside the doll at index 4 i.e. doll of size two in size three

We are left with two dolls of size three, which cannot be further placed inside each other. So, the output is 2.

Example #2

Input 1, 2, 2, 3, 4, 5
Output 2

Explanation: We can place dolls at index (1, 2, 4, 5) in the doll at index 6.
So, we will remain with two dolls of sizes two and five.

这是我的代码:

public int process(List<Integer> doll) {
    Map<Integer, Integer> map = new TreeMap<>();
    for(int key : doll) map.put(key, map.getOrDefault(key,0)+1);
    
    List<Integer> list = new ArrayList<>(map.keySet());
    int maxKey = list.get(list.size()-1);
    int m = map.get(maxKey);
    int result = 0;
    for(int k : map.keySet()) {
        if(k != maxKey) {
            int p = map.get(k);
            if(p > m){
                result += p - m;
            }
        }
    }
    result += m;
    return result;
}

在 7 个测试用例中，有 3 个失败，并且它们是隐藏测试用例，因此我无法看到这些用例。

如何解决这个问题？

Answer 1

I can put the smaller dolls inside the larger ones, but dolls of the exact same size cannot be placed inside each other.

基本上你需要找到最常见的娃娃尺寸，它等于剩余娃娃的数量。

因为只有重复的尺寸才会限制将较小尺寸的娃娃放入较大尺寸的娃娃后剩下的娃娃数量。

让我们考虑以下示例，其中包含 16 个娃娃，尺寸从 1 到 5:

   ---   SIZES   --- 
+----------------------+
|  1   2   3   4   5   | -> doll of size 5 containing [4, 3, 2, 1]
|      2   3   4   5   | -> doll of size 5 containing [4, 3, 2]
|      2   3   4   5   | -> doll of size 5 containing [4, 3, 2]
|          3   4       | -> doll of size 4 containing [3]
|          3           | -> empty doll of size 3
+----------------------+

将所有较小的娃娃放入大娃娃中折叠数据后，我们将拥有 5 个娃娃:

• 3 个尺寸为 5 的娃娃；
• 1 尺寸为 4 的娃娃；
• 1 尺寸为 3 的娃娃；

娃娃的总数受最常见尺寸的限制。

public static int process(List<Integer> doll) {
    Map<Integer, Integer> sizeByCount = new HashMap<>();
    
    for (int size : doll) {
        sizeByCount.merge(size, 1, Integer::sum); // or sizeByCount.put(size, sizeByCount.getOrDefault(size, 0) + 1);
    }
    
    int max = 0;
    
    for (int count : sizeByCount.values()) {
        max = Math.max(count, max);
    }
    
    return max;
}

如果您熟悉 Streams API，可以用一条语句替换此代码:

return doll.stream()
    .collect(Collectors.toMap(Function.identity(), e -> 1, Integer::sum))
    .values().stream()
    .max(Comparator.naturalOrder())
    .orElse(0);

main()

public static void main(String[] args) {
    System.out.println(process(List.of(1, 2, 2, 3, 4, 5)));
    System.out.println(process(List.of(2, 2, 3, 3)));
}

输出:

2
2