精华内容
下载资源
问答
  • 判断一个无序数列是否等差数列

    千次阅读 2017-03-03 10:55:59
    我的想法是只是判断一个数组是否为等差数列,相对来说容易好多。思路如下:  (1)对数组进行第一次遍历,找出数组中的min.max  (2)如果是等差数列,那么公差必然是(max-min)/(n-1) n为元素个数  (3)有了...

      这个题目是腾讯电话面试的考题之一:给定一个数组,不适用任何排序方法,快排什么的,判断出一个数列是否是等差数列,并且要求算法复杂度不得超过快排。

    我的想法是只是判断一个数组是否为等差数列,相对来说容易好多。思路如下:

      (1)对数组进行第一次遍历,找出数组中的min.max

      (2)如果是等差数列,那么公差必然是(max-min)/(n-1)   n为元素个数

      (3)有了公差,有了首项,有了尾项。这个等差数列实际上就模拟出来了。接下来就是判断是不是符合要求

      最后出来的程序,只是对数组做了两次遍历。时间复杂度为线性的,比快排(nlogn)少好多,尤其n相当大时。如果大家有其他的想法,可以交流一下,共同进步。同时,如果有什么不对的地方,批评指正。

    package perceptron;
    
    import java.io.IOException;
    import java.util.TreeMap;
    
    public class arithmetic {
    	public static void main(String[] args) throws IOException{
    		
    		double[] seq = {2,4,6,10};
    		judgeSeq(seq);
    	}
    	
    	public static void judgeSeq(double[] seq){
    		
    		double min = Double.MAX_VALUE;
    		double max = Double.MIN_VALUE;
    		for(int i=0;i<seq.length;i++){//对数组进行第一次遍历,找出数组中min ,max
    			if(seq[i]<min){
    				min = seq[i];
    			}
    			else if(seq[i]>max){
    				max = seq[i];
    			}
    		}
    
    		double Dif = (max-min)/(seq.length-1); //求得公差
    		
    		
    		
    		String flag = "True";
    		if(Dif==0){ //如果公差为0,那么说明数列中所有的数都是相同的 ,判断所有数是否相同
    			for(int i=0;i<seq.length;i++){
    				if(seq[i]!=min){
    					flag = "false";
    					break;
    				}
    			}
    			
    		}
    		else{//公差不为0
    			
    			TreeMap<Double,Integer> tm = new TreeMap<Double,Integer>();//建立容器,存储每个数字出现的次数
    			
    			for(int i=0;i<seq.length;i++){ 
    				
    				//统计每个谁出现的次数,因为公差不为0,必然不可能出现相同的数字
    				if(tm.get(seq[i])==null){
    					tm.put(seq[i], 0);
    				}
    				tm.put(seq[i],tm.get(seq[i])+1);
    				if(tm.get(seq[i])>1){
    					flag = "false";
    					break;
    				}
    				
    				
    				double DifNum = (seq[i]-min)/Dif; // 判断(seq[i]-min)/Dif是否为整数,在[0,seq.length-1]之间
    				int s = (int)DifNum;
    				if(DifNum-(double)s!=0||DifNum>seq.length||DifNum<0){
    					flag = "false";
    					break;
    				}
    			
    			}
    			
    		}
    		
    		if(flag.equals("True")){
    			System.out.println("属于等差数列");
    		}
    		else{
    			System.out.println("不属于等差数列");
    		}
    	}
    
    }
    

    展开全文
  • 判断一个数列不是等差数列,要比判断一个数列是等差数列比较容易。bool progressive = true; for (int i = 0; i () - 1; ++i){ if (A[i+1] - A[i] != A[1] - A[0]) progressive = false; }

    判断一个数列不是等差数列,要比判断一个数列是等差数列比较容易。

    bool progressive = true;
    for (int i = 0; i < A.size() - 1; ++i){
        if (A[i+1] - A[i] != A[1] - A[0]){
            progressive = false;
            break;
        }
    }

    当然也可以等差数列的性质:

    bool progressive = true;
    int d = A[1] - A[0]
    for (int i = 2; i < A.size(); ++i){
        if (A[i] != A[i-1] + d) {
            progressive = false;
            break;  
        }
    
    }
    展开全文
  • 如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。 小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置...

    题目描述
    如果一个数列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"。

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int main()
    {
        char str[] = "Possible";
        int *arr, n;
        int i, j, minIndex, tmp;
        scanf("%d", &n);
        arr = (int *)malloc(n*sizeof(int));
        for (i = 0; i < n; i++)
        {
            scanf("%d", arr + i);
        }
        // for (i = 0; i < n - 1; i++) 	//冒泡排序
        // {
        //     for (j = 0; j < n - 1 - i; j++)
        //     {
        //         if (*(arr + j) < *(arr + j + 1))
        //         {
        //             tmp = *(arr + j + 1);
        //             *(arr + j + 1) = *(arr + j);
        //             *(arr + j) = tmp;
        //         }
        //     }
        // }
    
        for (i = 0; i < n - 1; i++)	//选择排序
        {
            minIndex = i;
            for (j = i + 1; j < n; j++)
            {
                if (*(arr + j) < *(arr + minIndex))
                    minIndex = j;
            }
            tmp = *(arr + minIndex);
            *(arr + minIndex) = *(arr + i);
            *(arr + i) = tmp;
        }
        
        for(i = 0; i < n; i++)
        {
            printf("%d", *(arr + i));
        }
        printf("\n");
        minIndex = *(arr) - *(arr + 1);
    
        for (i = 0; i < n - 1; i++)
        {
            tmp = *(arr + i) - *(arr + i + 1);
            if (minIndex != tmp)
            {
                strcpy(str,"Impossible");
                break;
            }
            
        }
        printf("%s\n", str);
        
        return 0;
    }
    
    展开全文
  • 建模-判断一列数是不是等差数列

    千次阅读 2017-08-16 17:28:20
    如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。 小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个...

    题目:
    如果一个数列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;
    }
    展开全文
  • Go语言中文网,致力于每日...例如,如下三个数列即为等差数列:1, 3, 5, 7, 97, 7, 7, 73, -1, -5, -9如下数列不是等差数列:1, 1, 2, 5, 7现给定一个以0为起始索引,包含N个数的数组A。数组的切片(P, Q)为满足规则(...
  • 如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。 小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置...
  • Java蓝桥等差数列

    2020-03-04 16:56:34
    输入n,接下来输入n个数据...思路:先对数进行从小到大的排序,当两者之间的0时,两者之间最小的就是最大的公差数,在判断数列是否正确。 代码如下: import java.util.Scanner; public class cxl { public ...
  • 蓝桥杯省赛-等差数列

    2020-08-10 11:45:32
    等差素数列 2,3,5,7,11,13,…是素数序列。 类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。 上边的数列公差为30,长度为6。...就是筛选素数,然后依次加上公差再判断是否为素数,并累
  • 注意:当n=1时,构成长度1的等差数列。 说明 题目不难,但不加优化可能超时。先排序,枚举前两个数,然后得到公差。这样以后相当于得到了下一个数,继续枚举判断是否相等即可。 #include using ...
  • 题目描述:等差数列 思路 一开始拿到这道题的时候,我的...如果公差0,即该等差数列的每一项都相同,则答案为数组长度。 但是,我还是太天真了,太傻了,看了网上大佬的题解后,深感羞愧不如。 这道题其实考的...
  • n组数据就是fans选出的n组卡片,请你判断每一组卡片是否能构成等差数列. 输入 第一个数数据的组数n,表示后面有n行,每行中的第一个数该组数据的元素个数m(1≤m≤100),其后是m个正整数(不会超出int的表示...
  • 膜一下zkw神犇 另外fread真的快。。题目:...思路:难点就在于判断是否构成等差数列。我们可以用平方和的方式,Hash一下,然后和等差数列平方和公式算出来的值进行比对,如果不一致那么说明...
  • 给定n个整数,判断是否为等差数列。 输入 第一行是一个整数n(2<=n<=20),表示数列的长度。 第二行是n个空格分开的整数,每个数的绝对值均小于100000000。 输出 如果构成等差数列,输出“YES”,否则输出”NO”。...
  • range函数一个经常用到的函数,本质上来讲他是一个生成等差整数数列的函数,range函数可以使用3个参数:起始值,终止...间隔值是等差数列的公差,如果不写的话,默认1。 下面的程序演示了range函数1个参数、2个参...
  • 否则首先区间不能有重复,记录每个点的上一个与他权值相等的点的位置fro,区间取fro最大值之后判断是否在区间左边 然后设区间长度len,则区间最大值必须等于区间最小值+(len-1)*k 满足上边两个条件之后,只要...
  • 采用动态规划 dp[i][j]表示从i到j的子数组是否为等差数组 转移方程: dp[i][i+len]=dp[i][i+len-1]&&A[j]-A[j-1]==A[j-1]-A[j-2...len从3开始增加,判断每个长度的子数组是否为等差数组,并且依赖前面的状...
  • 网易2018校招内推编程题集合[编程题] 等差数列题目大概是:输入一个数列,可以任意交换位置,判断是否为等差数列。做题思路:输入数字,冒泡排序(小→大),逐个计算差值,差值不同则flag=0,循环终止,输出。注意...
  • 判断一个数是否为平方数

    千次阅读 2017-05-04 20:04:10
    判断一个数是否为平方数: 根据数学的等差数列求和公式: 由此可知:任意数的平方都能用一个初值为1,等差为2的等差数列表示,所以判断一个数是不是平方数可以用这个数不断的减2,如果最后减到为0,那么这个数...
  • 题目描述 对一个输入的序列S进行任意交换,并判断交换后的数列S能否成为等差数列。 输入描述 第一行:整数n,即数列的长度 如 Input: 3 第二行:n个元素的数组a[i],即数列中的每个整数
  • 牛客网-CCA的数列

    2020-12-20 20:37:34
    给定一个长度为 n 数列,判断是否为“牛”的,是则输出“YES”,否则输出“NO”。 一个数列是“牛”的,当且仅当其满足以下三个条件中至少一个: 1、这个数列是等差数列 2、这个数列是等比数列 3、这个数列是等...
  • 给定一个长度为 n 数列,判断是否为“牛”的,是则输出“YES”,否则输出“NO”。 一个数列是“牛”的,当且仅当其满足以下三个条件中至少一个: 1、这个数列是等差数列 2、这个数列是等比数列 3、这个数列是等...
  • 判断一个整数是否平方数

    千次阅读 2009-12-11 20:23:00
    我们知道:以1首项,2公差的等差数列的求和公式n^2. 所以要判断数K是否平方数,只须: 从该等差数列的左边开始,K不断的减数列的项,直至减不过为止。 此时如果k的值变为0,则k平方数,并且执行减法的...
  • 求一个数的因子数及平方数判断

    千次阅读 2018-08-14 20:04:40
    对于一个自然数N,都可以分解质因子得到如下形式: 怎么推出来的我也不知道。。。 ...其中因子数包含自身和1 ...根据数学的等差数列求和公式: 由此可知:任意数的平方都能用一个初值1,等差2的等差...
  • 题目大意给定一个11到NN的列,问是否存在一个长度33的子等差数列。N≤300000N \leq 300000解题思路看到这题,感觉有点无从下手,好像怎么要都要枚举两个值。 但是我们可以发现一个很神奇的性质如果对于一个位置ii...
  • leetcode周赛196(Java)

    千次阅读 2020-07-05 19:29:22
    1.判断能否形成等差数列 给你一个数字数组 arr 。 如果一个数列中,任意相邻两项的差总等于同一个常数,那么这个数列就称为 等差数列 。 如果可以重新排列数组形成等差数列,请返回 true ;否则,返回 false   很...

空空如也

空空如也

1 2 3 4 5
收藏数 88
精华内容 35
关键字:

判断数列是否为等差数列