arrays - n 变换后数组中相等元素的最大数量

Question

您有一个包含 n 个元素的数组。在任何移动中，您选择两个索引 i 和 j，i 不等于 j，并且在一个索引处增加值并在另一个索引处减小值。您可以多次进行此移动。我们需要的是可以具有相同值的元素的最大数量（在任意数量的移动之后）。1,2,3,4 答案的示例是 3，因为在应用移动任意次数后，我们最多可以有 3 个相等的元素。但我正在寻找算法来做到这一点，所以需要帮助。

Answer 1

如前所述，这并不需要太多的算法。如果您可以根据需要多次执行此操作，则应该始终能够获得其中一个N或N-1元素相等的结果（N输入数组的大小在哪里）。

取输入的总和。例如，在您的情况下：sum(1,2,3,4) = 10.

如果sum % N == 0，答案是N。在此之前的任何时候，您都会有至少一个高于sum/N和至少一个低于的元素。增加低点，减少高点。

否则答案是N-1。最后一个集合可以有N-1元素等于，(int)sum/N最后一个元素将是原始总和的余数。您可以使用最后一个元素作为“备用”来增加/减少您想要的任何其他元素。

由于您不必实际找到转换，因此最终结果是 O(N)。您只需将总和乘以 N 即可检查要给出的答案。除非您想找到导致答案的步骤序列，否则递归或搜索“平均对”是没有用的。

Answer 2

这可能是一个非常无效的算法 - 但您可以尝试某种动态编程。

def elems(array, previous_attempts = []):
    # Get a list of all the possible arrays (after transforming the current array)
    # and remove all of the arrays we have seen so far.
    possible_arrays = possibilities(array) - previous_attempts

    # If there are no more possible, return the number of elements the array
    # has in common.
    if possible_arrays is empty:
        return num_in_common(array)

    # Otherwise, for all the possibilities find the one that creates the maximum
    # amount of elements in common.
    max = 0
    for a in possible_arrays:
        # This is a recursive call that calculates the score for the possibility.
        # It also keeps track of the current state so we don't revisit it.
        score = elems(a, previous_attempts.append(array))
        if score > max:
            max = score
    return max

Answer 3

A您可以计算数组中每个值的出现次数（让我们调用size的数组N）。让任何值的最大出现次数为A（max可能是几个值），您只对出现max次数的值感兴趣，因为其他值无法max+1通过建议的方法超过出现次数。

极端情况：

1. 如果max=N答案是N
2. 如果max=N-1答案是N-1

V在所有其他情况下，对于出现次数的每个值max，您都试图找到其他两个具有平均值V但不等于的值V。如果它们存在，那么答案是max+2（您可以增加它们，使它们都等于V）。如果没有此类索引i并且j存在，则答案是max+1（您可以增加任意两个其他值，直到其中一个等于V）。

编辑： 这个答案假设你只选择一次，i然后j随心所欲地增加/减少它们（我想我误解了）。