我有一個數字陣列和另一個數字K。
我的任務是減少陣列中不同元素的數量。為此，我可以多次更新陣列。要更新陣列，我必須按照以下步驟操作：
選擇 index 處的元素i并將該元素添加K，并將所有其他剩余元素減少K。
為了更新陣列，我可以多次選擇相同的索引。
例子：
K = 1
Array: [3,1,3]
Answer: 3
我選擇 index = 1，因為 [3-1, 1 1, 3-1] = [2,2,2] 所以我們有出現 3 次的數字 2，所以這個元素出現的次數最多。所以答案是3。
另一個例子：
K = 1
Array: [1,2,2]
Answer: 2
不可能使所有元素都相同，所以我們有出現 2 次的數字 2，所以答案是 2。
陣列大小可以是[1, 1000]，陣列中K和元素的值在[0, 1000]范圍內
這是我嘗試過的代碼，我的方法不正確。
public static int process(int K, int[] A) {
Map<Integer, Integer> map = new TreeMap<>();
for (int key : A) {
map.put(key, map.getOrDefault(key, 0) 1);
}
int result = 0;
boolean flag = false;
int last = -1, cur = -1;
for (int key : map.keySet()) {
if (flag == false) {
flag = true;
last = key;
continue;
}
cur = key;
int a = map.get(last), b = map.get(cur);
if (Math.abs(last - cur) > K) {
result = a b;
} else {
result = Math.max(a, b);
}
}
last = cur;
return result;
}
uj5u.com熱心網友回復：
查看帶有 的示例時K = 1，很明顯答案取決于元素的奇偶性。只有奇偶性相同的元素才能設定為同一級別，所有奇偶性相同的元素都可以加入。
例如：
[2 4 6] -> [1 5 5] -> [2 4 4] -> [3 3 3]
[1 2 2] -> [2 1 1] ... no progress
有了K = 1，我們必須考慮取模 2 的值，即取模2*K。例如，
當K不K = 2等于 1 時，兩個數字只能相隔 4 的距離倍數，即2*K。
[2 6 6] -> [4 4 4]
對于不同于 1 的 K，我們不是為具有相同奇偶性的數字創建桶，而是根據值模 2K 創建桶。
我們只需要注意使用模數而不是余數，負值的值是不同的。
那么答案是否只是桶的最大大小。
輸出：
K = 1 Array : 3 1 3 -> 3
K = 1 Array : 1 2 2 -> 2
K = 1 Array : 2 3 4 7 4 9 11 -> 4
K = 1 Array : -3 -1 2 3 -> 3
K = 3 Array : -7 -1 0 1 2 4 5 -> 3
這是一個簡單的 C 代碼來說明該演算法。
在此代碼中，val_modulo計算每個元素的模 2K 值。
然后，增加相應的計數器
Bucket[val_modulo] = Bucket[val_modulo] 1
最后，最大值對應于重復次數最多的最終值的重復次數。
我們可能會注意到非空桶的數量對應于不同最終值的數量（未在此代碼中使用）。
#include <iostream>
#include <vector>
#include <string>
#include <map>
void print (const std::vector<int> &A, const std::string &after = "\n", const std::string &before = "") {
std::cout << before;
for (int x: A) {
std::cout << x << " ";
}
std::cout << after;
}
int Modulo (int n, int mod) {
int ans = n % mod;
if (ans < 0) ans = mod;
return ans;
}
int max_equal(int K, std::vector<int> A) {
K = std::abs(K); // useful befoe taking the modulo
std::map<int, int> Buckets;
int nmax = 0;
int mod = 2*K;
for (int x: A) {
int val_modulo = Modulo (x, mod); // and not x*mod, as x can be negative
Buckets[val_modulo] ;
}
for (auto x: Buckets) {
if (x.second > nmax) {
nmax = x.second;
}
}
return nmax;
}
int main() {
std::vector<std::vector<int>> examples = {
{3, 1, 3},
{1, 2, 2},
{2, 3, 4, 7, 4, 9, 11},
{-3, -1, 2, 3},
{-7, -1, 0, 1, 2, 4, 5}
};
std::vector<int> tab_K = {1, 1, 1, 1, 3};
for (int i = 0; i < examples.size(); i) {
std::cout << "K = " << tab_K[i] << " Array : ";
print (examples[i], " -> ");
auto ans = max_equal (tab_K[i], examples[i]);
std::cout << ans << "\n";
}
return 0;
}
uj5u.com熱心網友回復：
這個問題是概念性的，并將其轉換為某種計算代碼。
我們看看吧：
我們選擇一個數字（按索引，這是無關緊要的），并且對于所有出現我們添加K。所有其他我們減去K然后相同出現的次數必須是最大的。
當拾取的數字 k等于另一個數字 - k時，相同的發生只能生長。
資料結構：
以陣列編號為鍵的映射，并映射到頻率（數字在陣列中出現的頻率）。
所以：
PickNumber.value K = otherNumber.value - K
=> otherNumber.value = PickNumber.value 2* K
請注意，因為只有一個 otherNumber，派生自pickNumber。（它可能不止一次發生。）
我們想要最大：
pickedNumber.frequency otherNumber.frequency maximal.
雖然實際上并不需要 map，但排序陣列也可以，讓我們做一個 map：
演算法：
保持簡單。
int[] numbers = {3, 1, 3};
int index = pickedIndexOfBestSolution(numbers, 1);
System.out.println("Index: " index);
int pickedIndexOfBestSolution(int[] numbers, int k) {
Map<Integer, Long> frequencyTable = IntStream.of(numbers)
.boxed()
.collect(Collectors.groupingBy(Function.identity(),
Collectors.counting()));
int bestNumber = frequencyTable.entrySet().stream()
.sorted(Comparator.comparingLong(e -> -e.getValue()
- frequencyTable.getOrDefault(e.getKey() 2*k, 0L)))
.findFirst()
.map(e -> e.getKey())
.orElseThrow();
int index = -1;
while (numbers[ index] != bestNumber) {
}
return index;
}
我使用IntStreamand填充的頻率表groupingBy（就像 SQL 一樣）。作為counting與做long，我只是不停地說。
為了找到最大值，我計算了新的出現次數，并嘗試添加“其他”數字的頻率；0 當沒有其他數字時。我沒有使用.reverse()反向比較（最大，最大，第一個），而是取了負值，這對我來說似乎更具計算性。請注意，使用 findFirst 來查找最大值的 Stream 也可能是最優的：不需要流創建中間串列。
對于我使用蠻力（while回圈）的索引，一種indexOf.
請注意，如果沒有其他數字，它會回傳出現次數最多的數字的索引。這很好。
簡而言之：
您會看到不同的方法。實際上更簡單，更堅固。事實上，首先應用一些（次要）智能。試圖首先確定問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409393.html
標籤：