如何最好地判断一个数组是否为排列？

Question

给定一个由N个整数组成的非空数组A。排列是一个包含每个元素从1到N恰好一次的序列。 例如，[4,2,1,3]是一个排列，但[4,1,3]不是一个排列，因为缺少值2。 目标是检查输入数组A是否是一个排列。 限制条件： N是范围在[1..100,000]内的整数； A的每个元素都是范围在[1..1,000,000,000]内的整数。 我的代码：

# 1 = permutation 0 = not a permutation
def solution(A):
    total = sum(A)

    formula_total = (len(A)*(len(A)+1))/(2)

    if total == formula_total:

        return 1

    return 0

我的解决方案在Antisum上失败了（我不知道那是什么）。

- Harpreet Singh

---

你认为对total的限制是判定某个东西是否为排列的必要和充分条件吗？当你进行求和时会丢失很多信息。例如，1+3=2+2，所以你的想法似乎行不通。为什么不考虑排序呢？ - John Coleman

请注意，如果任何一个 A[i] 大于 N，则可以立即返回 0。您只需要一个大小为 N 的数组。将每个条目初始化为 0。扫描输入数组并递增 array[A[i]]。如果 array[A[i]] 是 2，则立即返回 0。 - user3386109

@JohnColeman 我原以为 total 会与前 N 个整数的和 formula_total 不同，但显然情况并非如此。 - Harpreet Singh

@HarpreetSingh 在测试的描述中明确说明了"antiSum"是什么：总和是正确的，但它不是一个排列，N <= 10。这正是为你这种算法设计的，因为使用你的代码[2, 2, 2]将返回true。 - ChatterOne

@ChatterOne 感谢您的解释。检查 len(set(A)) == len(A) 条件解决了我代码中的“antiSum”问题。 - Harpreet Singh

Answer 1

您可以检查列表的最小值是否为1，最大值是否等于列表的长度。然后可以将列表转换为集合以检查长度是否相等，如果是，则列表中的所有项都是唯一的，因此该列表是您认为的排列：

def solution(A):
    return min(A) == 1 and max(A) == len(A) == len(set(A))

所以：

print(solution([4,2,1,3]))
print(solution([4,1,3]))
print(solution([4,2,1,4]))
print(solution([4,2,5,3]))

输出：

True
False
False
False

如果您想将1和0作为返回值，可以将布尔值传递给int()构造函数：

def solution(A):
    return int(min(A) == 1 and max(A) == len(A) == len(set(A)))

- blhsing

---

我认为如果给定一个内部损坏的数组，比如 [1, 2, 2, 4]，这个方法会失败。我们不能保证输入值已经是唯一的。 - Prune

不会因为输入值不唯一而失败，因为它不会通过“len(set(A)) == len(A)”测试，该测试正是用来确保输入值是唯一的。 - blhsing

糟糕！我错过了 set 调用。谢谢。 - Prune

谢谢，我在我的代码中添加了 if len(set(A)) != len(A): return 0，现在我的函数已经通过了所有的测试用例。 - Harpreet Singh

@HarpreetSingh 我已经更新了我的答案，提供了返回 1 和 0 的解决方案，如果这正是你所需要的，请将其标记为被接受的答案（点击答案旁边的灰色勾号）。 - blhsing

Answer 2

这只是一个简单版本的变位词问题。将输入数组进行排序，与由1到N的元素组成的数组进行比较是否相等。返回比较的布尔值结果。

如果需要线性解决方案，则声明一个大小为N的布尔类型数组seen。迭代处理输入数组，并在处理过程中计算元素个数。

对于每个元素A：

• 如果A不在1-N范围内则返回失败
• 如果seen[A]为真则返回失败
• seen[A] = 真

最后，返回count == N。换句话说，如果count == N，则我们已经找到了每个整数；返回真。否则，返回假（在这种情况下，计数会小于N）。

- Prune

Answer 3

def getMax(A):
    max_ele = 0
    for each_integer in A:
        max_ele = max(max_ele,each_integer)
    return max_ele

def restoreArray(A):
    for idx, val in enumerate(A):
        A[idx] = abs(A[idx])

def solution(A):
    max_ele = getMax(A)
    if len(A) != max_ele:
        return False
    for idx, val in enumerate(A):
        if A[abs(A[idx]) - 1] < 0:
            # restore the array back   
            restoreArray(A)
            return False
        else:
            A[abs(A[idx]) - 1] = -A[abs(A[idx]) - 1]

    # restore the array back   
    restoreArray(A)
    return True


print(solution([4,2,1,3]))
print(solution([4,1,3]))
print(solution([4,2,1,4]))
print(solution([4,2,5,3]))
print(solution([1,2,3,4]))
print(solution([1,2,3,4,6,7,2]))
print(solution([9,2,3,4,6,7,5,8,1]))
print(solution([9,2,3,4,6,7,5,8,1,10,6]))

输出：

True
False
False
False
True
False
True
False

算法：

• 我们可以利用所有元素都是正数的限制。
• 因此，我们遍历数组并通过使特定索引处的整数为负来标记索引为已访问。
• 现在，如果我们遇到一个指向另一个已经为负的索引的索引，则返回False。
• 如果我们从未遇到这种情况，那么它肯定是一个排列，我们返回True。
• 我们将数组恢复回来，以便不会就地修改它。
• 时间复杂度：O(n)，空间复杂度：O(1)。
• 您可以使该解决方案更具Python风格（因为我不是Python爱好者），我留给您作为练习。

- nice_dev

---

从概念上讲，我喜欢这个想法（+1），但我怀疑在CPython中基于set()的解决方案会更有效率，因为由C编写的函数会处理重要的工作，而不是解释器运行循环。 - John Coleman

Answer 4

这里最快的解决方案是使用

import numpy as np

# create integer array `data`

seen = np.zeros(len(data), dtype=bool)
seen[data] = True
is_permutation = np.all(seen)

如@Prune所建议的。排序并与arange比较的建议要慢大约20倍。

---

重现图表的代码：

import numpy as np
import perfplot


def setup(n):
    return np.random.permutation(np.arange(n))


def sort(data):
    return np.sort(data) == np.arange(len(data))


def seen(data):
    seen = np.zeros(len(data), dtype=bool)
    seen[data] = True
    return np.all(seen)


def min_max_set(data):
    return min(data) == 0 and max(data) + 1 == len(data) == len(set(data))


b = perfplot.bench(
    setup=setup,
    kernels=[sort, seen, min_max_set],
    n_range=[2 ** k for k in range(23)],
    xlabel="len(array)",
)
b.save("out.png")
b.show()

- Nico Schlömer