删除给定迭代次数的元素

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

这是一个建议的方法。value构建从到的映射count_of_value找出有多少值的计数不能被 整除k。这count_incommensurate是你无法摆脱的价值观。对于剩余的值，通过递增计数创建一个数组count_of_value / k。现在创建一个查找，按迭代次数，有多少可删除的值。执行查找。在您的情况下，这些步骤会产生以下结果。初始地图为：{&nbsp; &nbsp;&nbsp;&nbsp;0:&nbsp;1,&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1:&nbsp;2,&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2:&nbsp;1,&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;5:&nbsp;1, }k=1可被so整除的所有值count_incommensurate = 0。按升序排列的计数数组是[1, 1, 1, 2]。现在我们来到查找数组。0它从计数总数开始，即4.&nbsp;所以[4, ...。现在我们将每个数字写入递减前的计数次数，并在 0 处停止。所以我们得到[4, 3, 2, 1, 1]。换句话说counts:&nbsp;[1,&nbsp;1,&nbsp;1,&nbsp;2&nbsp;&nbsp;&nbsp;] lookup:&nbsp;[4,&nbsp;3,&nbsp;2,&nbsp;1,&nbsp;1]如果我们的计数是，[1, 2, 3]我们会得到counts:&nbsp;[1,&nbsp;2&nbsp;&nbsp;&nbsp;,&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;] lookup:&nbsp;[3,&nbsp;2,&nbsp;2,&nbsp;1,&nbsp;1,&nbsp;1]但回到我们实际得到的。&nbsp;[4, 3, 2, 1, 1]是一个用于我们查找的从 0 开始的数组，最后的所有内容都是0.现在进行查找。查找1加不相称给了我们3 + 0 = 3。查找5结束，所以我们得到了0 + 0 = 0。查找3给我们1 + 0 = 1。如果我们用 重复这个练习，k=2我们会发现count_incommensurateis3并且我们的查找数组最终变成[1].&nbsp;（零次迭代后，该元素1仍然存在。）由于所有查找都结束了，我们将得到3, 3, 3答案。这个算法的时间是O(N + Q)。鉴于需要O(N)扫描值和O(Q)扫描查询，您只能通过一个常数因子来真正改进它。需要提及的一点是，需要对初始计数数组（[1, 2, 1, 1]在本例中）进行排序，这会增加O(N log N)问题的时间复杂度。

Answer 2

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;class Main {&nbsp; &nbsp; public static void main(String args[] ) throws Exception {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; BufferedReader br = new BufferedReader(new InputStreamReader(System.in));&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; String[] num_arr;&nbsp; &nbsp; &nbsp; &nbsp; num_arr = br.readLine().split("\\s");&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; int [] nkq_arr = new int[3];&nbsp; &nbsp; &nbsp; &nbsp; for(int i=0;i<3;i++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nkq_arr[i] = Integer.parseInt(num_arr[i]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; int N = nkq_arr[0];&nbsp; &nbsp; &nbsp; &nbsp; int K = nkq_arr[1];&nbsp; &nbsp; &nbsp; &nbsp; int Q = nkq_arr[2];&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; int i = 0,j = 0;&nbsp; &nbsp; &nbsp; &nbsp; String[] param_arr;&nbsp; &nbsp; &nbsp; &nbsp; param_arr = br.readLine().split("\\s");&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; int [] arr = new int[N];&nbsp; &nbsp; &nbsp; &nbsp; while(i < N)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[i] = Integer.parseInt(param_arr[i]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; int[] queries = new int[Q];&nbsp; &nbsp; &nbsp; &nbsp; while(j < Q)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; queries[j] = Integer.parseInt(br.readLine());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for(int c=0;c<Q;c++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println(minFeatures(arr,N,K,queries[c]));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; static int minFeatures (int [] arr, int N, int K, int query)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();&nbsp; &nbsp; &nbsp; int count=0;&nbsp; &nbsp; &nbsp; for(int i=0;i<N;i++)&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(!map.containsKey(arr[i]))&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map.put(arr[i],1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Integer b = map.get(arr[i]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b+=1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map.replace((Integer)arr[i],b);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; List<Integer> relevant_arr = new ArrayList();&nbsp; &nbsp; &nbsp; int improper_count=0;&nbsp; &nbsp; &nbsp; int relevant_arr_length = 0;&nbsp; &nbsp; &nbsp; for(Integer val : map.values())&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(val%K==0)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; relevant_arr.add(val/K);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; relevant_arr_length++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; improper_count++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; Collections.sort(relevant_arr);&nbsp; &nbsp; &nbsp; List<Integer> lookUp_arr = new ArrayList();&nbsp; &nbsp; &nbsp; int alpha = 0;&nbsp; &nbsp; &nbsp; int overall_length=0;&nbsp; &nbsp; &nbsp; while(alpha < relevant_arr_length)&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int number_of_times = relevant_arr.get(alpha);&nbsp; &nbsp; &nbsp; &nbsp; int beta = number_of_times;&nbsp; &nbsp; &nbsp; &nbsp; while(beta > 0)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lookUp_arr.add(count);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; beta--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; overall_length++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; count--;&nbsp; &nbsp; &nbsp; &nbsp; alpha++;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; if(query > overall_length-1)&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; return improper_count;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; return improper_count + lookUp_arr.get(query);&nbsp; &nbsp; &nbsp; }&nbsp; }}

Answer 3

建议的算法的 Python 实现。from collections import defaultdictdef evaluateMin(arrQ,k,queryArr):&nbsp; ans = []&nbsp; countMap = defaultdict(lambda : 0)&nbsp; for value in arrQ:&nbsp; &nbsp; countMap[value] +=1&nbsp;&nbsp;&nbsp; counts=[]&nbsp; presentEveryTime = 0&nbsp; for value in countMap:&nbsp; &nbsp; if countMap[value] % k != 0:&nbsp; &nbsp; &nbsp; presentEveryTime +=1&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; counts.append(int(countMap[value]/k))&nbsp; # Creating Lookup Array&nbsp; counts = sorted(counts)&nbsp; lookup = []&nbsp; # print(counts)&nbsp; appender = len(counts)&nbsp; for count in counts:&nbsp; &nbsp; for i in range(count):&nbsp; &nbsp; &nbsp; lookup.append(appender)&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; if appender != 1:&nbsp; &nbsp; &nbsp; appender -=1&nbsp; # print(lookup,presentEveryTime)&nbsp; for query in queryArr:&nbsp; &nbsp; if query >= len(lookup):&nbsp; &nbsp; &nbsp; ans.append(0+presentEveryTime)&nbsp; &nbsp; else:&nbsp;&nbsp; &nbsp; &nbsp; ans.append(lookup[query]+presentEveryTime)&nbsp; return ansprint(evaluateMin([5,0,1,2,1,1,1],2,[1,5,3,0,2]))