Arithmetic Progressions(暴力 hash_map)

Arithmetic Progressions(暴力 hash_map)

 

 题意:给你N个数,求这些数能组成的等差数列的最长的长度。

思路:暴力,每个 a[ i ],当成首项,然后求枚举 a[i+1]-a[i]=d,在来一层for循环,从i+1开始,检查从i+1到N有多少以d为公差的数,这里需要用hash_map标记一下,如果用map的复杂度是O(logn),hash_map的复杂度是O(1)。

Arithmetic Progressions(暴力 hash_map)
#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include <hash_map>
using namespace std;
using namespace __gnu_cxx;
const int N=5e3+10;
const double eps=1e-7;
typedef long long  ll;
int n,l;
int a[N];
int main()
{
    int n;
    scanf("%d",&n);
    hash_map <int,int>q;
    for(int i=0; i<n; i++)
    {

        scanf("%d",&a[i]);
        q[a[i]]=1;
    }
    sort(a,a+n);
    int sum=-5;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            int tp1=a[i];
            int d=a[j]-a[i];
            int ans=1;
            while(1)
            {
                int tp2=tp1+d;
                if(tp2>a[n-1])
                    break;
                if(q[tp2]!=0)
                {

                    ans++;
                    tp1=tp2;
                }
                else
                    break;
            }
            if(sum<ans)
                sum=ans;
        }
    }
    printf("%d\n",sum);

}
View Code

 

 

上一篇:Android(java)学习笔记44:Map集合的遍历之键值对对象找键和值


下一篇:林轩田机器学习基石笔记6 - Theory of Generalization