我有一个数字阵列和另一个数字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时，相同的发生只能生长。
资料结构：
以阵列编号为键的映射，并映射到频率（数字在阵列中出现的频率）。
所以：
请注意，因为只有一个 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.
请注意，如果没有其他数字，它会回传出现次数最多的数字的索引。这很好。
简而言之：
您会看到不同的方法。实际上更简单，更坚固。事实上，首先应用一些（次要）智能。试图首先确定问题。
0 评论