一道算法题--判断数字序列是否连续

    今天在网上看到一算法题，说是微软面试题，题目如下：

一个整数数列，元素取值可能是0—65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6；
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4；
- 0可以多次出现；
- 复杂度如果是O(n2)则不得分。


   思考了下，觉得可以这样认为：

   由于0可以重复出现，而且可以充当任何数字使用，就把它看做一个魔法豆吧，每个魔法豆可以满足我们一个愿望，只是这个愿望只能是你想要的数字。我们不妨假设序列是排好序的，那么我们可以从第二个不为零的数字开始向后遍历，比较它与前面一个是否连续，如果不连续则使用一颗魔法豆，让这颗豆变成我们想要的数字（如果此时豆子用完了，也就说明不连续），连续则继续向后比较。

一.   算法：

   1. 对给定序列进行排序

   2. 遍历序列到第一个不为零的数字为止，统计零的个数，也就是我们的豆子数

   3. 从第二个不为零的数字开始，判断与前一个数字的连续性

二. 算法实现：

#include <stdlib.h>

int intCmp ( const void *a , const void *b )
{
    return *(int *)a - *(int *)b;
}

/*
 * datas, input sequence
 * num, size of sequence
 * return value:
 * 1, is successive
 * 0, not successive
 */
int isSequence(int *datas, const int num)
{
    int zero_num = 0;   //number of 0
    int last = 0;
    int i = 0;          //iterator
    int iret = 1;       //is successive
    
    //sort sequence
    qsort(datas, num, sizeof(int), intCmp);
    
    //find number for the first that is not 0
    while (i < num)
    {
        if (datas[i])
        {
            last = datas[i];
            break;
        }
        ++zero_num;
        ++i;
    }
    
    //through the sequence from position i+1, and find gaps
    ++i;
    while (i < num)
    {
        if (1 != datas[i]-last)
        {//not successive
            if (0 == zero_num)
            {//no magics
                iret = 0; // this sequence is not successive
                break;
            }
            
            //consume one magic bean
            --zero_num;
            last += 1;
            continue;
        }
        //successive
        last = datas[i++];
    }
    
    return iret;
}

三. 算法分析

 

    该算法很容分析，主要分为两大部分：排序 和 遍历统计检查。快速排序咱们知道它平均性能是非常高的，尽管其最差也是O(n2)；遍历部分复杂度则为 O(n)，显然该算法效率主要取决于排序部分，即为O(n2)，平均性能 nlgn。但是我们知道，我们一直都是用快速排序是因为看重它的平均性能，在序列随机的情况下，相信该算法还是很好的。如果非要以最差性能评价，换个排序算法就OK了，比如堆排序等。