Skip to content

Latest commit

 

History

History
75 lines (54 loc) · 2.91 KB

15.3 CountTriangles.md

File metadata and controls

75 lines (54 loc) · 2.91 KB
Raw

Lesson_15 Caterpillar method

P15.3 CountTriangles

Count the number of triangles that can be built from a given set of edges.

  • P15.3 三角形的数量

计算给定的数组可以构建为三角形的数量

给定一个由N个整数组成的数组A。三联体(P, Q, R)是三角形的，如果可以建立一个边长为A[P], A[Q]和A[R]的三角形。换句话说，如果0≤P<Q<R<N，则称三联体(P, Q, R)是三角形的，并且：

  • 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]=12

这个数组的元素可以构成四个三角形的三联体，，即（0，2，4），（0，2，5），（0，4，5）和（2，4，5）。

编写函数：

def solution(A)

给定一个由N个整数组成的数组A，则返回该数组中是三角形的三联体的数目。

例如，针对上面的例子，函数应该返回4。

假定：

  1. N是区间[0，1,000]内的整数；
  2. 数组A的每个元素都是区间[1，1,000,000,000]内的整数；

  • 解题思路

首先将A排序，排序不影响元素大小，因此也不会影响结果。排序的好处在于：对于排序后的数组B，索引a<b<c，如果B[a]+B[b]>B[c]，则说明(a,b,c)可以组成三角形，并且对于b和c之间的任何索引d而言，三联体(a,b,d)也一定可以组成三角形，因此继续增加索引c，直到(a,b,c)不能构成三角形。如果B[a]+B[b]>B[c]不成立，说明需要增大索引b，如果b没有增大的空间(b<c需要成立)，则同时增大索引b和索引c。

  • Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 15：Caterpillar method
# P 15.3 CountTriangles


def solution(A):
    """
    返回数组A的元素可以构成三角形的个数。
    :param A: 数组
    :return: 构成三角形的个数
    """
    #  首先将A进行排序
    A.sort()
    count_triangle = 0
    for index, value in enumerate(A):
        middle_idx = index + 1
        biggest_idx = index + 2
        while biggest_idx < len(A):
            if value + A[middle_idx] > A[biggest_idx]:  # 此时可以构成三角形
                count_triangle += biggest_idx - middle_idx  # 最大值到中间值之间的均能构成三角形
                biggest_idx += 1  # 增大最大值
            elif middle_idx < biggest_idx - 1:  # 够不成三角形，如果中间值较小，则试着增加中间值
                middle_idx += 1
            else:  # 如果中间值没有增加的余地，则同时增加中间值，和最大值。因为只增加最大值，还是够不成三角形
                biggest_idx += 1
                middle_idx += 1
    return count_triangle

  • 结果

image