文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡(jiǎn)書

1. Description

Can Make Arithmetic Progression From Sequence

2. Solution

解析：Version 1，先排序，再判斷其是否是算術(shù)(等差)數(shù)組。Version 2以空間換時(shí)間，找出最大最小值，最大最小值相等，則數(shù)全相同為等差數(shù)列，如果最大最小值之差不能整除數(shù)組長(zhǎng)度減1，說明是非等差數(shù)列。構(gòu)造等差數(shù)列，判斷其是否是數(shù)組中的元素。

• Version 1

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        if len(arr) == 2:
            return True
        arr.sort()
        for i in range(2, len(arr)):
            if arr[i] - arr[i-1] != arr[i-1] - arr[i-2]:
                return False
        return True

• Version 2

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        if len(arr) == 2:
            return True
        stat = {}
        minimum = arr[0]
        maximum = arr[0]
        for x in arr:
            minimum = min(minimum, x)
            maximum = max(maximum, x)
            stat[x] = x
        if maximum - minimum == 0:
            return True
        if (maximum - minimum) % (len(arr) - 1) != 0:
            return False
        step = (maximum - minimum) // (len(arr) - 1)
        for x in range(minimum, maximum+1, step):
            if x not in stat:
                return False
        return True

Reference

1. https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/