[Leetcode] 1502. Can Make Arithmetic Progression From Sequence (Easy)

概述

題目

https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/
問數列是否能組成等差數列

心得

很直覺式題目，排序後確認兩兩間隔是否相等即可 (差值為 0 亦是等差數量)

Sort

思路

先排序後確認間距

程式

class Solution(object):
    def canMakeArithmeticProgression(self, arr):
        """
        :type arr: List[int]
        :rtype: bool
        """
        arr.sort()
        diff = arr[1] - arr[0]
        for i in range(len(arr)-1):
            if arr[i+1] - arr[i] != diff:
                return False
        return True

Complexity

Time Complexity: O(n log n)
有排序故 n log n

Space Complexity: O(1)
基本上無使用到額外空間

Math

思路

透過數學，確認最大最小值與其中間平均分配數字，是否都在同個集合中，時間複雜度為 O(n)

程式

class Solution(object):
    def canMakeArithmeticProgression(self, arr):
        """
        :type arr: List[int]
        :rtype: bool
        """
        n = len(arr)
        ast = set(arr)
        if len(ast) != n:
            if len(ast) == 1:
                return True
            return False

        mxv, mnv = max(arr), min(arr)
        dif = (mxv - mnv) // (n-1)

        for c in range(mnv, mxv+1, dif):
            if c not in ast:
                return False
        return True