Codility每周一课：L4 Counting Element

P4.1 PermCheck

Check whether array A is a permutation..

• P4.1 判断排列

判断数组A是否是一个排列

包含从1到N的每个整数，并且每个整数只包含一次的序列称为排列。数组A是由N个整数组成的数组。

例如，数组A：A[0]＝4，A[1]＝1，A[2]＝3，A[3]＝2是一个排列，但数组如果为：A[0]＝4，A[1]＝1，A[2]＝3，则不是排列，因为缺少值2。

编写函数：

def solution(A)

如果数组A是排列，则返回1；如果不是排列，则返回0。

例如，给定数组A：A[0]＝4，A[1]＝1，A[2]＝3，A[3]＝2，返回1；给定数组A[0]＝4，A[1]＝1，A[2]＝3，返回0。

假定：
1. N是区间[1，100000]内的整数；
2. 数组A的每个元素都是区间[1，100000000]内的整数；

• 解题思路

  利用字典以及判断list是否相等。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 4：Counting Elements
# P 4.1 PermCheck

def solution(A):
    """
    判断数组是否是一个排列, 时间复杂度O(N) or O(N * log(N))
    :param A: N个整数组成的数组
    :return: 是排列返回1，不是返回0
    """
    if sorted(A) == list(range(1, len(A)+1)):
        return 1
    else:
        return 0

• 结果