給定一個整數數組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();}
3 回答
至尊寶的傳說
TA貢獻1789條經驗 獲得超10個贊
這是一個建議的方法。
value構建從到的映射count_of_value找出有多少值的計數不能被 整除
k。這count_incommensurate是你無法擺脫的價值觀。對于剩余的值，通過遞增計數創建一個數組
count_of_value / k。現在創建一個查找，按迭代次數，有多少可刪除的值。
執行查找。
在您的情況下，這些步驟會產生以下結果。初始地圖為：
{
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)問題的時間復雜度。
白衣染霜花
TA貢獻1796條經驗 獲得超10個贊
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);
}
}
}
慕桂英3389331
TA貢獻2036條經驗 獲得超8個贊
建議的算法的 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]))
添加回答
舉報
0/150
提交
取消