Skip to content

6.3 Triangle.md

Latest commit

 

History

History
72 lines (46 loc) · 1.94 KB

6.3 Triangle.md

File metadata and controls

72 lines (46 loc) · 1.94 KB

Lesson_6 Sorting 排序

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.3 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