给定一个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();
}
最佳答案
这里有一个建议的方法。
构建从value
到count_of_value
的映射
找出有多少个值的计数不能被k
整除这个count_incommensurate
就是你不能去掉的值。
对于其余值,通过递增计数创建一个count_of_value / k
数组。
现在,根据迭代次数创建可删除值的查找。
做你的检查。
在您的情况下,这些步骤将导致以下结果。最初的地图是:
{
0: 1,
1: 2,
2: 1,
5: 1,
}
可被
k=1
socount_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
'现在我们来查一下。
lookup
1
加上不公度给了我们3 + 0 = 3
。lookup
5
已结束,因此我们得到0 + 0 = 0
。lookup
3
为我们提供了1 + 0 = 0
。如果我们用
k=2
重复这个练习,我们会发现count_incommensurate
是3
并且我们的查找数组最终是[1]
(经过零次迭代后,元素1
仍然存在。)由于所有查找都结束了,我们将得到3, 3, 3
作为答案。该算法的时间是
O(N + Q)
。考虑到扫描值需要O(N)
,而扫描查询则需要O(Q)
,因此您不能在这个基础上真正提高一个常量因子。