我有一个数字阵列和另一个数字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.

请注意，如果没有其他数字，它会回传出现次数最多的数字的索引。这很好。

简而言之：

您会看到不同的方法。实际上更简单，更坚固。事实上，首先应用一些（次要）智能。试图首先确定问题。