如何寻找最大的覆盖点

  坐标轴上从左到右的点为a[0],a[1],a[2],…,a[n-1]，设一根木棒的长度为L，求L最多能覆盖坐标轴的几个点？ 分析：   直接从左到右扫描，使用两个索引i和j，i从位置0开始，j从位置1开始，如果a[j]-a[i]<=L，则j++前进，并记录中间经过的点的数。，如果a[j]-a[i]>L，则j–回退，覆盖点的个数-1，回到刚好满足条件的时候，将满足条件的最大值与前面找出的最大值比较，记录下当前的最大值，然后执行i++,j++,直到求出最大的点个数。

两个点需要注意：

1）这里不可能存在i和j使得a[j]-a[i]刚好等于L的情况发生，所以，判断条件不能为a[j]-a[i]==L。 2）可能存在不同的覆盖点但覆盖的长度相同的情况发生，此时只选取一次覆盖的点。 实现代码：

package lock; public class T11 { public static int maxCover(int a[],int L) { int count=2; int maxCount=1; int start=0; int n=a.length; int i=0,j=1; while(i<n&&j<n) { while((j<n)&&(a[j]-a[i]<=L)) { j++; count++; } j--; count--; if(count>maxCount) { start=i; maxCount=count; } i++; j++; } System.out.print("覆盖的坐标点: "); for(i=start;i<start+maxCount;i++) { System.out.print(a[i]+""); } System.out.println(); return maxCount; } public static void main(String[] args) { // TODO Auto-generated method stub int a[]= {1,2,7,8,10,12,13,15,16,17,19,25}; System.out.print("最长覆盖点数:"+maxCover(a,8)); } }

运行结果：

算法分析：

  这种方法的时间复杂度为O(N),其中，N为数组的长度。