[数据结构与算法]算法：判断能否形成等差数列

leetcode 判断能否形成等差数列

给你一个数字数组 arr 。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。

如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

代码：

void quiksort(int * arr, int start, int end) {
    if (start < end) {
        int left = start, right = end;
        int tmp = arr[start];
        while (left < right) {
            while (left < right && arr[right] >= tmp) right--;
            if (left < right) {
                arr[left] = arr[right];
                left++;
            }
            while (left < right && arr[left] < tmp) left++;
            if (left < right) {
                arr[right] = arr[left];
                right--;
            }
        }
        arr[right] = tmp;
        quiksort(arr, start, right - 1);
        quiksort(arr, right + 1, end);
    }
}

bool canMakeArithmeticProgression(int* arr, int arrSize){

    int tmp = arr[1] - arr[0];
    for (int i = 2; i < arrSize; i++) {
        if ((arr[i] - arr[i - 1]) != tmp) {
            quiksort(arr, 0, arrSize - 1);
            tmp = arr[1] - arr[0];
            for (i = 2; i < arrSize; i++) { 
                if ((arr[i] - arr[i - 1]) != tmp) return false;
            }
        };
    }
    return true;
}

这里特别注意，如果当前数组不是一个等差数列，还需要对其进行排序，再判断其是否为等差数列。

其中，一个问题，可不可以先对其进行排序，然后再判断？当然可以，但是会对其性能进行影响，当前数组已经是一个有序的了，再对其进行排序，就是浪费时间。

我这里先对其进行判断，假设其已经是一个有序的，如果出现不相等的项，再对其进行排序，重新从头开始判断。

结果