删除给定迭代次数的元素

Question

给定一个整数数组N。遍历整个数组，选出 K 个包含相同值的位置。K然后从阵列中删除这些选定的。如果我们无法选择K值，则无法从数组中删除任何位置。任务是最小化每次迭代后数组中可用的不同整数的数量。对于给定的Q查询，每个查询都有一个数字P。对于每个查询，在进行迭代后打印数组中存在的不同整数的数量P。1<= N <= 10^61<= K <= 101<= Q <= 10^50<= C <= 10^51 <= P <= NExample:N=5K=1Q=3Array = [5,0,1,2,1];Queries (Various P values):153Output:301P = 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. 执行查找。

在您的情况下，这些步骤会产生以下结果。初始地图为：

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

k=1可被so整除的所有值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_incommensurateis3并且我们的查找数组最终变成[1]. （零次迭代后，该元素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 {

    public static void main(String args[] ) throws Exception {

           

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        

        String[] num_arr;

        num_arr = br.readLine().split("\\s");

        

        int [] nkq_arr = new int[3];

        for(int i=0;i<3;i++)

        {   

            nkq_arr[i] = Integer.parseInt(num_arr[i]);

        }

        int N = nkq_arr[0];

        int K = nkq_arr[1];

        int Q = nkq_arr[2];

        

        int i = 0,j = 0;

        String[] param_arr;

        param_arr = br.readLine().split("\\s");

        

        int [] arr = new int[N];

        while(i < N)

        {

            arr[i] = Integer.parseInt(param_arr[i]);

            i++;

        }

        int[] queries = new int[Q];

        while(j < Q)

        {

            queries[j] = Integer.parseInt(br.readLine());

            j++;

        }

        for(int c=0;c<Q;c++)

        {

          System.out.println(minFeatures(arr,N,K,queries[c]));

        } 

    }

    static int minFeatures (int [] arr, int N, int K, int query)

    {

      HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

      int count=0;

      for(int i=0;i<N;i++)

      {

        if(!map.containsKey(arr[i]))

        {

          map.put(arr[i],1);

          count++;

        }

        else

        {

          Integer b = map.get(arr[i]);

          b+=1;

          map.replace((Integer)arr[i],b);

        }

      }

      

      List<Integer> relevant_arr = new ArrayList();

      int improper_count=0;

      int relevant_arr_length = 0;

      for(Integer val : map.values())

      {

        if(val%K==0)

        {

          relevant_arr.add(val/K);

          relevant_arr_length++;

        }

        else

        {

          improper_count++;

        }

      }

      Collections.sort(relevant_arr);

      List<Integer> lookUp_arr = new ArrayList();

      int alpha = 0;

      int overall_length=0;

      while(alpha < relevant_arr_length)

      {

        int number_of_times = relevant_arr.get(alpha);

        int beta = number_of_times;

        while(beta > 0)

        {

          lookUp_arr.add(count);

          beta--;

          overall_length++;

        }

        count--;

        alpha++;

      }

      

      if(query > overall_length-1)

      {

        return improper_count;

      }      

      else

      {

        return improper_count + lookUp_arr.get(query);

      }

  }

}

Answer 3

建议的算法的 Python 实现。

from collections import defaultdict

def evaluateMin(arrQ,k,queryArr):

  ans = []

  countMap = defaultdict(lambda : 0)

  for value in arrQ:

    countMap[value] +=1

  

  counts=[]

  presentEveryTime = 0

  for value in countMap:

    if countMap[value] % k != 0:

      presentEveryTime +=1

    else:

      counts.append(int(countMap[value]/k))

  # Creating Lookup Array

  counts = sorted(counts)

  lookup = []

  # print(counts)

  appender = len(counts)

  for count in counts:

    for i in range(count):

      lookup.append(appender)

    

    if appender != 1:

      appender -=1

  # print(lookup,presentEveryTime)

  for query in queryArr:

    if query >= len(lookup):

      ans.append(0+presentEveryTime)

    else: 

      ans.append(lookup[query]+presentEveryTime)

  return ans

print(evaluateMin([5,0,1,2,1,1,1],2,[1,5,3,0,2]))