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; }