java - 删除给定迭代次数的元素

Question

给定一个包含 N 个整数的数组。遍历整个数组，选出 K 个包含相同值的位置。然后从数组中删除这些选定的 K。如果我们无法选择 K 值，则无法从数组中删除任何位置。

任务是最小化每次迭代后数组中可用的不同整数的数量。

对于给定的Q 查询，每个查询都有一个数字P。对于每个查询，在执行 P 次迭代后打印数组中存在的不同整数的数量。

1<= N <= 10^6
1<= K <= 10
1<= Q <= 10^5
0<= C <= 10^5
1 <= P <= N

Example:
N=5
K=1
Q=3

Array = [5,0,1,2,1];

Queries (Various P values):
1
5
3

Output:
3
0
1

P = 3时的解释:

1. First iteration, we can remove element 1 with value `5`.
2. Second iteration, we can remove element 2 with `0`.
3. Third iteration, we can remove element 4 with value `2`.

最后，数组只包含两个值为 1 的元素。 因此剩余的不同颜色数为 1。

这是我试过的代码，但一直卡在如何满足要求上:

static int getDistinctFeatures(int[] array, int size, int K, int P) {
    Map<Integer, Integer> map = new LinkedHashMap<>();
    // Count the occurrence of each element in the array
    for (int i : array) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }

    Set<Integer> keys = map.keySet();
    List<Integer> keyList = new ArrayList<>(keys);

    int index = 0;

    for (int i = 0; i < P && index < keyList.size(); i++) {
        int key = keyList.get(index);
        index++;
        int count = map.get(key);
        if (count == 1) {
            map.remove(key);
        } else {
            // What to do here
        }
    }
    return map.size();
}

Answer 1

这是一个建议的方法。

1. 构建从value到count_of_value的映射
2. 找出有多少值的计数不能被 k 整除。此 count_incommensurate 是您无法摆脱的值的数量。
3. 对于剩余的值，通过递增计数创建一个数组，count_of_value/k。
4. 现在创建一个查询，按迭代次数查找有多少个可删除值。
5. 执行查找。

在您的情况下，这些步骤会产生以下结果。初始 map 是:

{
    0: 1,
    1: 2,
    2: 1,
    5: 1,
}

可被 k=1 整除的所有值，因此 count_incommensurate = 0。

递增顺序的计数数组是[1, 1, 1, 2]。

现在我们来到查找数组。它从 0 开始，计数总数为 4。所以 [4, ...。现在我们将每个数字写入递减前的计数次数，并在 0 处停止。因此我们得到 [4, 3, 2, 1, 1]。也就是说

counts: [1, 1, 1, 2   ]
lookup: [4, 3, 2, 1, 1]

如果我们的计数是[1, 2, 3]，我们就会得到

counts: [1, 2   , 3      ]
lookup: [3, 2, 2, 1, 1, 1]

但回到我们实际得到的东西。 [4, 3, 2, 1, 1] 是一个从 0 开始的数组，用于我们的查找，最后的所有内容都是 0。

现在进行查找。

查找 1 加上不相称给我们 3 + 0 = 3。

查找 5 结束，所以我们得到 0 + 0 = 0。

查找 3 给我们 1 + 0 = 1。

如果我们用 k=2 重复这个练习，我们会发现 count_incommensurate 是 3 并且我们的查找数组最终是 [1]。 (零次迭代后，元素 1 仍然存在。)由于所有查找都结束了，我们将得到 3, 3, 3 作为我们的答案。

这个算法的时间是O(N + Q)。鉴于它需要 O(N) 来扫描值，而 O(Q) 来扫描查询，你不能真正改进它超过一个常量因素。需要提及的一个小点是初始计数数组(在本例中为[1, 2, 1, 1])需要排序，这增加了时间复杂度O( N log N) 问题。