Codility每周一课：L6 Sorting(P6.3)

0.png

P6.3 Triangle
Determine whether a triangle can be built from a given set of edges.

• P6.3 三角形
  判断给定的数组是否可以组成三角形

由N个整数组成的数组A。三元组(P, Q, R)是三角形的，如果0≤P<Q<R<N，并且： A[P]+A[Q]>A[R]，A[Q]+A[R]>A[P]，A[R]+A[P]>A[Q]成立。

例如，考虑数组A：A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20

三元组（0，2，4）是三角形的。因为0<=0<2<4，并且10<5+8，5<10+8，8<10+5。

编写函数：

def solution(A)

一个数组A包含N个整数，如果该数组存在一个三角形的三元组，则返回1，否则返回0。

例如，针对上面的例子，函数应该返回1；
针对如下数组：A[0]=10，A[1]=50，A[2]=5，A[3]=1,函数应返回0。

假定：

1. N是区间[0，100000]内的整数；
2. 数组A的每个元素都是区间[-2147483648，2147483647]内的整数。

• 解题思路

逆序排列数组，如果前面的小于后面两数的和，则可以组成三角形的。并且这三个数中不能由0或者负数。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 6：Sorting
# P 6.2 Triangle


def solution(A):
    """
    判断数组中的任何三元组对应的三个数是否是三角形的,时间复杂度为O(N*log(N))
    :param A: 数组
    :return: 返回结果
    """
    if len(A) < 3:
        return 0
    else:
        A.sort(reverse=True)
        for index, value in enumerate(A[:-2]):
            if A[index+2] <= 0:
                return 0
            else:
                if value < A[index+1] + A[index+2]:
                    return 1
        return 0

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image