建模-判断一列数是不是等差数列

题目: 如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。 小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列。

输入要求: 输入包括两行,第一行包含整数n(2 ≤ n ≤ 50),即数列的长度;第二行n个元素x[i](0 ≤ x[i] ≤ 1000),即数列中的每个整数。

输出要求: 如果可以变成等差数列输出”Possible”,否则输出”Impossible”。

例如 输入: 3 3 1 2 输出: Possible

解题思路: 在各种各样的编程题中,有些是直接给出要求,比如从尾到头打印链表,我们只看题目就可以一抹了然,数据结构是链表,要求是从后向前打印。但是有时给的更像是一个应用题,这就好比小学时一个水管放水,一个水管注水的问题一样,好神奇…..这是网易的一道题目,说了半天就是要判断一列数字是不是等差数列,由于没有插入与删除操作,一个顺序存储结构就可以啦。 我们可以试着这样来解决,找到一列数(n个)中的最大max和最小min,如果max=min,则为公差为0的等差数列,如果不相等那么公差就是max-min/n-1,如果没办法除尽的话,那么不是等差数列,如果除尽,即求出公差error。 现在我们知道了一个数列的最大值,最小值,个数和公差,这样就知道了等差数列的每一个数,那么下面就可以逐个判断这些数是不是在数组中,由于不是排序的数组,二分法啥的也就用不了了,所以时间复杂度是O(n^2),那么有没有其他的方法可以优化时间复杂度呢? 由于我们知道数组中的最小值,那么如果是等差数列的话,数组中的每个数与最小值的差值,对error取模的结果应该都是0,这样我们就可以判断一列数是不是等差数列了,时间复杂度为O(n)。

代码实现:

#include "iostream"    
using namespace std;

int main()
{
    int str[50];
    int num;
    cin>>num;
    for (int i = 0;i<num;i++)
        cin>>str[i];
    int maxvalue =0;
    for (int i = 0;i<num;i++)
    {
        if (maxvalue<str[i])
          maxvalue=str[i];
    }
    int minvalue =maxvalue;
    for (int i = 0;i<num;i++)
    {
        if (minvalue>str[i])
            minvalue=str[i];
    }
    if (maxvalue==minvalue)
    {
        cout<<"Possible"<<endl ;
        return 0;
    }
    int flag =  (maxvalue-minvalue)%(num-1);
    if (flag != 0)
    {
            cout<<"Impossible"<<endl ;
            return 0;
    }
    int error =(maxvalue-minvalue)/(num-1);
    for (int j=0;j <num;j++)
    {
        if ((str[j]-minvalue)%error !=0)
            cout<<"Impossible"<<endl;
    }
    cout<<"Possible"<<endl;
    return 0;
}  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发技术

排序之堆排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

632
来自专栏ml

HDUOJ-----(1251)统计难题

统计难题 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Jav...

3489
来自专栏ml

HDUOJ-----4506小明系列故事——师兄帮帮忙

小明系列故事——师兄帮帮忙 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3276...

2727
来自专栏人工智能LeadAI

算法 | 排序算法图形化比较:快速排序、插入排序、选择排序、冒泡排序

用Objective-C实现几种基本的排序算法,并把排序的过程图形化显示。其实算法还是挺有趣的 。 选择排序 冒泡排序 插入排序 快速排序 01 选择排序 以升...

2867
来自专栏趣谈编程

神速Hash

面试官: 聊聊HashMap的底层实现 理解HashMap底层,首先应该理解Hash函数,今天我们聊聊什么是Hash函数以及Hash函数的设计 查找速度的困扰 ...

1615
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第11章 时间序列11.1 日期和时间数据类型及工具11.2 时间序列基础11.3 日期的范围、频率以及移动11.4 时区处理时区本地化和转换11.5 时期及其

时间序列(time series)数据是一种重要的结构化数据形式,应用于多个领域,包括金融学、经济学、生态学、神经科学、物理学等。在多个时间点观察或测量到的任何...

4746
来自专栏青玉伏案

算法导论之插入排序和归并排序

  作为一名前线的码农不时地看一下算法和数据结构还是很有必要的,虽然《算法导论》这本书很难啃,但还是有必要啃一下的。算法这东西和某种编程语言关系不大,在大学的课...

2067
来自专栏落影的专栏

程序员进阶之算法练习(十六)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。 正文 5. L...

3615
来自专栏智能算法

前端面试中的常见的算法问题

作者:Jack Pu 链接:www.jackpu.com/qian-duan-mian-shi-zhong-de-chang-jian-de-suan-fa-w...

4298
来自专栏数据结构与算法

1430 素数判定

1430 素数判定 题目描述 Description 质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。 素数在数论中有...

3436

扫码关注云+社区