刷题笔记#4——数列排列数论

文章寄语

在末日中，人们总想寻找希望，但要真有希望的话，那还叫末日吗？
　　　　　　　　　　　　　　　　　　　　——《灵笼》

引言

现在起每日一题更名为刷题笔记

好久没写笔记了，加上最近比较空遂用hexo的主题搭了一个开源博客，以后有什么都会写在这里。

题目描述

给你一个数字数组arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为等差数列
如果可以重新排列数组形成等差数列，请返回 true否则，返回 false
1
2
3
输入: arr = [3,5,1]
输出: true
解释：对数组重新排序得到[1,3,5]或者[5,3,1]，任意相邻两项的差分别为2或-2，可以形成等差数列。

虽然这道题是简单题，但是有两种方法值得我们去思考。

第一种是先排序后判断，也就是常规的思路。第二种是用数论的方法，可以直接判断，可以先判断在排序。

方法和思路

方法一：先排序后判断(模拟)

因为等差数列，我们把它排好序后，是否等差我们一眼可知。

思路

我们可以直接使用c++的内置函数sort()进行排序，因为等差数列的条件是相邻两项的差总等于同一个常数。所以为我们在排序完成后，还需要遍历一遍数据。

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) 
    {
        //对数组进行排序
        sort(arr.begin(), arr.end());
        //遍历数组进行判断
        for (int i = 1; i < arr.size() - 1; ++i) 
        {
            //如果中间项和左右两边的差值不是一个恒定的数，则不是等差数列，遂跳出
            if (arr[i] * 2 != arr[i - 1] + arr[i + 1]) 
                return false;
        }
        return true;
    }
};

因为排序的时间代价为O(nlog⁡n)，遍历序列的时间代价是 O(n)，故渐进时间复杂度为 O(nlog⁡n+n)=O(nlog⁡n)

方法二：直接判断且不需要排序(数论)

等差数列的成立条件如下：

①相邻两项的差值等于一个常数，也就是我们说的公差d
②公差d必须为整数(仅对本题而言，因为输入是整数，公差不会是小数)
③全部的项中不会存在重复的数据
④公差d可以为0，也就是所有项都是同一个数

思路

我们先对这个数列进行一次遍历，在题目所给的一串待处理数字中找到最大值和最小值。

为什么要找这个最大值和最小值呢？我们假设这串数字就是等差数列，则这个最大值和最小值就是数列的末项和首项。

知道了最大值和最小值，项数我们也知道了(输入几项就是几),我们可以套公式求出公差d。

公差d = (末项 - 首项)/(项数 - 1)

现在公差d已经被算出来了，对算出来的这个公差d进行一次判断

若首项 = 末项(最大值等于最小值)，说明数列每一项都一样，直接返回true，不用求出d。
若公差是小数，则不满足成立条件②，直接返回false。

接下来我们倒序再次遍历一遍这个数列。求出每一项减去首项然后除以公差d的商。

为什么这么做？因为在一个真正的等差数列中，每一项减去首项的差，对于公差d都是成倍数关系的。

等差数列通项公式：An = 首项 + (第n项 - 1) * 公差d

首项已经知道了，就是数组的最小值，公差我们也算出来了，An是第n项的值，也知道了。

现在的目的就是试图求n，即这个数字在整个数列中的位次。

但是因为有成立条件③的存在，直接判断会导致这个问题。所以我们开一个哈希集合，哈希集合不可以存放重复数据，正好可以判断。开其他的也可以。

若n是小数，直接返回false。因为没有第小数项，除非他在另一个次元.返回false。
若n在哈希中存在，说明数列内有重复，不满足条件③，返回false。

若当前数字通过两者，都坚持下来了，说明这个数字独立，加入到集合里。查看下一个数字。

如果循环结束还没有返回false，说明数列满足等差数列成立的所有条件。它确实是等差数列。返回true。

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        int arrlen = arr.size() - 1;
        int min = 1000001;
        int max = -1000001;
        int diff, result;
        unordered_set<int> numset;
        //有内置的函数可以直接取最大最小值，我这里没用
        for (int i = 0; i <= arrlen; ++i)
        {
            if (arr[i] < min)
                min = arr[i];
            if (arr[i] > max)
                max = arr[i];
        }
        //公差为0时
        if (min == max)
            return true;
        //公差是小数，即无法整除
        if ((max - min) % arrlen != 0)
            return false;
        //求公差
        diff = (max - min) / arrlen;
        for (int i = arrlen; i >= 0; --i)
        {
            //位次是小数
            if ((arr[i] - min) % diff != 0)
                return false;
            else
            {
                result = (arr[i] - min) / diff;
                //判断哈希表里是否已经存在数字
                if(numset.count(result) == 1)
                    return false;
                //没有就插入这个数字
                numset.insert(result);
            }
        }
        return true;
    }
};

拓展

其实这道题到这里就结束了，都知道了这几个元素在排序后数列的确切位置。

其实就可以反向排序了。

结语和留言

文章结语

梦比现实更易侵蚀人的精神，刻意准备的梦是危险的。
　　　　　　　　　　　　　　　　　　　　——东方绀珠传 ~ Legacy of Lunatic Kingdom.

笔记完毕编辑完毕时间CST 6.14 22:35

最后修改于8.15 00:20

蝠池茶园