力扣代码学习日记八

Problem: 1502. 判断能否形成等差数列

思路

给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

示例 1：

输入： arr = [3,5,1]
输出： true
解释： 对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
1
2
3

示例 2：

输入： arr = [1,2,4]
输出： false
解释： 无法通过重新排序得到等差数列。
1
2
3

提示：

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

解题方法

1. 首先，找出数组中的最小值和最大值。
2. 然后，计算等差数列的公差 d。为了得到公差，我们可以使用公式 d = (max - min) / (n - 1)，其中 n 是数组中的元素数量。
3. 创建一个新的数组，从最小值开始，每次增加公差 d，直到达到最大值，应该能得到 n 个元素
4. 如果新数组的长度与原始数组的长度不同，或者有任何一个元素在原始数组中的出现次数与新数组中不匹配，那么返回 false。
5. 否则，返回 true。

复杂度

时间复杂度:

1. 找出最小值和最大值: 这需要遍历数组一次，所以时间复杂度为 O(n)，其中 n 是数组中的元素数量。
2. 计算公差: 这是一个常数时间操作，所以时间复杂度为 O(1)。
3. 生成等差数列的集合: 这需要遍历 n 个元素一次，每次添加操作是 O(1)，因此总时间复杂度为 O(n)。
4. 比较两个集合: 在最坏的情况下，每个元素都需要比较一次，所以时间复杂度为 O(n)。

综上所述，总的时间复杂度为 O(n) + O(1) + O(n) + O(n) = O(n)。

空间复杂度:

1. 存储最小值和最大值: 这是常数空间，因此空间复杂度为 O(1)。
2. 生成等差数列的集合: 在最坏的情况下，会生成一个与原数组等大的集合，因此空间复杂度为 O(n)。
3. 比较集合时使用的空间: 如果使用了集合进行比较，则可能需要额外的空间来存储第二个集合，这也是 O(n)。

因此，总的空间复杂度是 O(n) + O(n) = O(n)。

代码

class Solution(object):
    def canMakeArithmeticProgression(self, arr):
        """
        :type arr: List[int]
        :rtype: bool
        """
        min_arr = min(arr) #最小数
        max_arr = max(arr) #最大数
        n = len(arr) #数组长度

        if (max_arr - min_arr) % (n - 1) !=0: #差是否能整除
            return False
        
        d = (max_arr - min_arr) // (n - 1) #计算差值
        if d == 0:
            return True
        
        expecte_set= set(min_arr + d * i for i in range(n)) #生成新数组

        return expecte_set == set(arr) #两个数组进行比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20