计算一个未排序数组中排序后相邻元素的最大差值

题目描述

请设计一个复杂度为O(n)的算法，计算一个未排序数组中排序后相邻元素的最大差值。

给定一个整数数组A和数组的大小n，请返回最大差值。保证数组元素个数大于等于2小于等于500。

测试样例：

[9,3,1,10],4

返回：6

 

class MaxDivision {
public:
 int findMaxDivision(vector<int> A, int n) {
        make_heap(A.begin(),A.end());
        sort_heap(A.begin(),A.end());
        int max = 0,tmp;
        for(int i=1;i<n;i++)
        {
            tmp = A[i]-A[i-1];
            max = tmp>max ? tmp:max;
        }
        return max;
    }
};

不明白上述方法为什么可以通过调试？？？？

 

class MaxDivision {
public:
    int findMaxDivision(vector<int> A, int n) {
        // write code here
        set<int> s;
        set<int>::iterator iter;
        set<int>::iterator iter2;
        for(int i=0;i<n;i++)
            s.insert(A[i]);
        iter=s.begin();
        int max=0;
        int first=*iter;
        int second=*iter;
         
        for(iter=s.begin();iter!=s.end();++iter)
        {
            if(*iter>first)
            {
                second=*iter;
                if(second-first>max)
                {
                    max=second-first;
                }
                first=second;
            }           
        }
        return max;
 
    }
};

 

最适合的方法是桶排序：

1.找出最大值和最小值。

2.生成一个最大值-最小值的区间 比如最大值9，最小值3，那就需要7个桶 

3.往里面填

4.查找空桶，最多的即为最大差值。

public static int findMaxDivision(int[] A, int n) {
    int maxnum = A[0];
    int minnum = A[0];
    for (int i = 0; i < A.length; i++) {
        if (maxnum < A[i])
            maxnum = A[i];
        if (minnum > A[i])
            minnum = A[i];
    }
    int[] arr = new int[maxnum - minnum + 1]; // 生成桶
    for (int i = 0; i < A.length; i++) {
        arr[A[i] - minnum]++; // 填桶
    }
    int count = 0;
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 0) { // 桶为空
            count++;   //记录连续空桶数
        } else {
            if (max < count)
                max = count;
            count = 0;
        }
    }
    return max+1;  //如最大值为9，最小值为3，中间有5个空桶，但差值应为6
}

　　

https://www.nowcoder.com/questionTerminal/376ede61d9654bc09dd7d9fa9a4b0bcd