给定一个由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上失败了(我不知道那是什么)。
total
的限制是判定某个东西是否为排列的必要和充分条件吗?当你进行求和时会丢失很多信息。例如,1+3=2+2
,所以你的想法似乎行不通。为什么不考虑排序呢? - John ColemanA[i]
大于N
,则可以立即返回 0。您只需要一个大小为N
的数组。将每个条目初始化为 0。扫描输入数组并递增array[A[i]]
。如果array[A[i]]
是 2,则立即返回 0。 - user3386109total
会与前 N 个整数的和formula_total
不同,但显然情况并非如此。 - Harpreet Singh[2, 2, 2]
将返回true。 - ChatterOnelen(set(A)) == len(A)
条件解决了我代码中的“antiSum”问题。 - Harpreet Singh