给定一个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();
}

最佳答案

这里有一个建议的方法。
构建从valuecount_of_value的映射
找出有多少个值的计数不能被k整除这个count_incommensurate就是你不能去掉的值。
对于其余值,通过递增计数创建一个count_of_value / k数组。
现在,根据迭代次数创建可删除值的查找。
做你的检查。
在您的情况下,这些步骤将导致以下结果。最初的地图是:

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

可被k=1socount_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'
现在我们来查一下。
lookup1加上不公度给了我们3 + 0 = 3
lookup5已结束,因此我们得到0 + 0 = 0
lookup3为我们提供了1 + 0 = 0
如果我们用k=2重复这个练习,我们会发现count_incommensurate3并且我们的查找数组最终是[1](经过零次迭代后,元素1仍然存在。)由于所有查找都结束了,我们将得到3, 3, 3作为答案。
该算法的时间是O(N + Q)。考虑到扫描值需要O(N),而扫描查询则需要O(Q),因此您不能在这个基础上真正提高一个常量因子。

09-10 03:19
查看更多