2013年07月26日

定长线段最多覆盖点的个数


定长线段最多覆盖点的个数

此题是在翻勇幸的百度面经文章后看到的。题目描述如下:

给定一系列的X轴的点坐标,例如1,3,7,8,9,11,这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数是多少?

分析

其实题目不难,是百度一面的题,最直接的方法,就是暴力来解决,首先从array[0]开始遍历数组,找出绳子能包含的点数,然后array[1],依次这样下去。还是更好的方法,用两个指针来处理,一个指针指前面,一个指后面,如果两个指针的差距小于4,前面的指针移动,如果大于或等于4,后面的移动。

代码

int coverMaxPoints(int *array, int len, int seglen){
    if(array == NULL || len <=0 || seglen < 0)
        return -1;
    int i = 0,j = 0;
    int max = 0, current = 0, count = 1;
    while(j < len - 1){
        if(current + array[j+1] - array[j] <= seglen){
            current += array[j+1] - array[j];
            j++;
            count++;
            if(count > max)
                max = count;
        }else{
            current -= array[i+1] - array[i];     
            i++;
            count--;
        }
    }

    return max;
}

随后对比了下勇幸的代码,发现自己的写得太不简练了,也没有很好的理解前后两个指针,还有变量命名有些欠缺,然后再重新写了一遍。

int coverMaxPointV2(int *array, int len, int seglen){
    if(array == NULL || len <=0 || seglen <= 0)
        return 0;

    int front = 0, rear = 0, max = 1; 
    while(front < len){
        while(front < len && array[front] - array[rear] <= seglen){
            ++front;
        }
        max = (front - rear) > max ? (front - rear) : max;
        ++rear;
    } 
    return max;
}

这样简炼多了,直接可以用下标差表示点的个数了,不要判断两个数之差然后再来统计点的个数。

总结

使用两个指针的好处是只需要遍历两遍就OK,两个指针分别走一遍,复杂度是O(N),如果如前面使用暴力解法,则复杂度最坏情况下是O(MN),如果存在很多相邻的数之间的差距大于1,则不需要比较M次,再最好的情况下复杂度也是O(N)。

前一篇: 火车运煤问题 后一篇: 最长公共子串