2018/4/15今日头条笔试第一题
第一题求递增数组a的最小周期T不知道哪里出了问题一直不通过，求助大佬
我的思路是这样的：
因为任意x∈a 若x+T<an 则x+T∈a任意x-T>a1则x-T∈a
如果不是求最小周期显然an-a1可以为T的最大取值（因为除了a1外的数加上T超过了数组的最大值）
那么可以先让T为an-a1然后看an-1-a1，an-2-a1，an-3-a1...... ......是否可以满足，满足则更新T
那么令r=n-1,T的初始值为an-a1，然后Tn=ar-a1
从i=2开始查看ai+Tn是否在数组内若在则i++不在则r--，Tn=ar-1-a1若在则继续，直到出现ai+Tn>an则让T=Tn然后r--重复该过程直到r=0
最后得出的T为要求的最小周期
代码如下：
public static long getT(long a[],Set<Long>set)
{
if(a.length<=1)
{
return 0;
}
int r=a.length-1;
long T=a[r]-a[0];
r--;
long nT=a[r]-a[0];
int i=1;
while (r>0)
{
long m=a[i]+nT;
if (m>=a[a.length-1])
{
T=nT;
r--;
nT=a[r]-a[0];
i=1;
}
else
{
if(set.contains(a[i]+T))
{
i++;
}
else
{
r--;
i=1;
}
}
}
return T;
}
腾讯公司福利 857人发布
