python - 确定给定数组的任何排列是否使长度为 K 的所有子数组的总和相等

Question

我在一次采访中被问到这个问题。

You are given an array consisting of N integers. You need to determine whether any permutation of a given array exists such that the sum of all subarrays of length K are equal. N is divisible by K i.e. N mod K = 0.
If the array is [1,2,1,3,2,3] and K = 2, it is False.
If the array is [1,2,1,3,2,3] and K = 3, it is True.

我的逻辑是这样的。

1) If N == K, return True.
2) Else store each of the distinct element in the array in a dictionary. If the number of distinct elements in the dictionary is greater than K, return False.
3) Else store the count of each distinct element in the dictionary.
4) If the count of any distinct element is less than (N/K), return False.
5) Finally return True.

这是我的 Python 代码:

def check(nums, n, k):
if n == k:
    return True
else:
    my_dict = {}
    for i in nums:
        if i not in my_dict:
            my_dict[i] = 1
        else:
            my_dict[i] += 1
    if len(my_dict) > k:
        return False
    count = int(n/k)
    for i,j in my_dict.items():
        if j < count:
            return False
    return True  

我的做法是否正确？有更好的方法吗？

Answer 1

您的解决方案几乎是正确的。问题是，元素计数需要被 n / k 整除。 .

证明

假设我们得到了一个满足条件的排列。对于任何不同的元素，很容易观察到，如果在 i 的排列中找到它, 也必须在以下位置找到它:i - k, i - 2k,... ,i mod k和 i + k, i + 2k,.., n - k + (i mod k) ，因此出现在 i暗示暗示出现在i % k < k .现在，在索引低于 k 的位置出现每个不同的事件暗示n / k总次数(这里 n mod k = 0 很重要)。

OP 解决方案的反例

一个会破坏你解决方案的例子(几乎肯定是最小的):

n = 8, k = 4 array = [1, 1, 1, 2, 2, 2, 2, 2]