方法一:排序

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(),arr.end());
        int diff = arr[1] - arr[0];
        for(int i = 1;i < arr.size();i++)
        {
            if(arr[i] - arr[i-1] != diff)
                return false;
        }
        return true;
    }
};

运行效率:

Runtime: 4 ms, faster than 65.12% of C++ online submissions for Can Make Arithmetic Progression From Sequence.
Memory Usage: 9 MB, less than 46.18% of C++ online submissions for Can Make Arithmetic Progression From Sequence.

方法二:

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        unordered_set<int> uset(arr.begin(),arr.end());
        int max = *max_element(arr.begin(),arr.end());
        int min = *min_element(arr.begin(),arr.end());
        if((max - min) %(arr.size() - 1) != 0)
            return false;
        int step = (max - min) /(arr.size() - 1);
        for(int i = min + step;i < max;i += step)
        {
            if(uset.find(i) == uset.end())
                return false;
        }
        
        return true;
    }
};

运行效率:

Runtime: 4 ms, faster than 65.12% of C++ online submissions for Can Make Arithmetic Progression From Sequence.
Memory Usage: 9.7 MB, less than 5.36% of C++ online submissions for Can Make Arithmetic Progression From Sequence.

评论区看到大神的解法:

class Solution
{
public:
    bool canMakeArithmeticProgression(vector<int>& arr)
    {
        if (arr.size() <= 2) return true;
        int min = INT_MAX, max = INT_MIN;
        for (int num : arr) {
            min = std::min(min, num);
            max = std::max(max, num);
        }
        if ((max - min) % (arr.size() - 1) != 0) return false;
        int d = (max - min) / (arr.size() - 1);

        int i = 0;
        while (i < arr.size()) {
            if (arr[i] == min + i * d) i++;
            else if ((arr[i] - min) % d != 0) return false;
            else {
                int pos = (arr[i] - min) / d;
                if (pos < i || arr[pos] == arr[i]) return false;
                std::swap(arr[i], arr[pos]);
            }
        }
        return true;
    }
};

运行效率:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Can Make Arithmetic Progression From Sequence.
Memory Usage: 8.8 MB, less than 78.41% of C++ online submissions for Can Make Arithmetic Progression From Sequence.