2019-01-14

经典数据结构题（一）

1、排序问题
有一个整形数组A，请设计一个时间复杂度为O(n)的算法，算出排序后相邻两数的最大差值。给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素个数大于等于2小于等于500。
测试样例：
[9,3,1,10],4 返回：6
思路：先排序，再遍历数组求出相邻2个数的差，保留最大值即可，此时时间复杂度为O(nlogn)。由于非线性时间比较类排序时间复杂度不能突破O(nlogn),因此使用桶排序的思想，对于n个数，设置n+1个桶，具体的，先遍历数组找出min和max，差值区间设置为d=（max-min）/n，于是区间是[min_{min+d）；[min+d}min+2d）……[min+(n-1)d~min+nd）这n区间，再单独为最大值max设置一个桶，于是得到n+1个桶，已知数组元素总共有n个，但是桶有n+1个，并且元素min必定在第一个桶中，max必定在n+1号桶中；显然要把n个元素放入到n+1个桶中必定会产生空桶，已知数组中的元素时整数，而虽然每个桶区间不一定是整数，例如[23/7，31/7)，但是没有关系，对于任意一个元素，它总会落入到某一个桶中，并且可以知道，不同桶之间元素的差值必定大于d,同一个桶中的元素的差值必定小于d，于是可知要求元素之间的最大差值只需要在不同的桶之间寻找，不用在同一个桶中寻找，并且题目要求是排序后相邻2个元素的最大差值，于是应该寻找2个相邻非空桶中前一个桶的最大值与后一个桶的最小值之间的差值，遍历所有桶，比较得到所有差值中的最大值就是结果所要求的相邻2数最大差值。

注意理解：最终要对每2个非空的相邻的桶求差值，而不能根据空桶的数目来确定2个相邻桶的差值，因为桶的长度可能是小数，那么间隔2个空桶和间隔3个空桶并不意味着后者具有更大的差值，因此应该对所有相邻的非空桶根据前桶的最大值和后桶的最小值求出差值作为比较对象，因此在遍历时对于每一个桶，要求出这个桶中元素的最大值maxOfBucket[i]，最小值minOfBucket[i]，并且保留上一个非空桶的maxOfLastBucket，于是差值着2个相邻非空桶的差值就是result= minOfBucket[i]- maxOfLastBucket；然后将当前桶的maxOfBucket[i]最为下一个桶的maxOfLastBucket。逐步替换result，当遍历完成时就可以得到最大差值。

int getBucketID(int num ,int min, int max,int n){
      return (int) (num - min) *n /(max - min);
}
int maxGap(int A[],int n){
    int maxValue = A[0];
    int minValue = A[0];
    for (int i = 0; i < n; i++) {
        if (maxValue < A[i])maxValue = A[i];
        if (minValue > A[i])minValue = A[i];
    }
    int* mins = (int*)malloc(sizeof(int)*(n + 1));
    int* maxs = (int*)malloc(sizeof(int)*(n + 1));
    int* hasNum = (int*)malloc(sizeof(int)*(n + 1));
    for (int k =0 ; k < n + 1; k++) {
            hasNum[k] = 0;
    }
    int bucketID = 0;
    int i = 0;
    for (;i < n; i++) {
        bucketID = getBucketID(A[i],minValue, maxValue,n);
        if (hasNum[bucketID] == 1) {
            if (mins[bucketID] > A[i]) {
                mins[bucketID] = A[i];
            }
            if (maxs[bucketID] < A[i]) {
                maxs[bucketID] = A[i];
            }
        }else{
            mins[bucketID] = A[i];
            maxs[bucketID] = A[i];
        }
         hasNum[bucketID] = 1;
    }
    int maxGap = 0;
    int lastMax = 0;
    i = 0;
    while (i < n + 1) {
         //找到一个空桶,记录下前一个桶的最大值
        while (i < n + 1 && hasNum[i] == 1) {
            i++;
        }
        if (i == n + 1)break;
        lastMax = maxs [i-1];
        while (i < n + 1 && hasNum[i] == 0) {
            i++;
        }
        if (i == n + 1)break;
        if (maxGap <= mins[i] - lastMax) {
            maxGap = mins[i] - lastMax;
        }
    }
   free(mins);
   free(maxs);
   free(hasNum);
    return maxGap;
}

2、最大差值
有一个长为n的数组A，求满足0≤a≤b<n的A[b]-A[a]的最大值。 给定数组A及它的大小n，请返回最大差值。
测试样例： [10,5],2 返回：0
思路： 从后向前和前边的最小数的差值，记录下来。最后遍历记录的数值找最大的。

int maxDivision(int A[],int n){
   int maxValue = 0;
   int minValue = A[0];
   int temp;
   for (int i = 1;i < n;i++) {
       if ((temp = A[i] - minValue) > maxValue) {
           maxValue = temp;
       }
       if (minValue > A[i]) {
           minValue = A[i];
       }
   }
   return maxValue;
}