2015.1.23 15:00

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Solution:

　　This here is not an O(n) solution, but O(n * log(n)). Sort the array and find the maximal gap.

　　As for a linear solution, I'm searching for it...

　　Discussions online said it could be solved using bucket sort, but that doesn't really satisfy O(n) time scale, right? At least I wouldn't take it for O(n).

Accepted code:

1 // 1AC, not an O(n) solution, though, one not yet come up with... 2 #include 
     
       3 using namespace std; 4  5 class Solution { 6 public: 7     int maximumGap(vector
      
        &num) { 8         sort(num.begin(), num.end()); 9         int n;10         11         n = (int)num.size();12         if (n < 2) {13             return 0;14         }15         16         int i;17         int ans = abs(num[0] - num[1]);18         for (i = 2; i < n; ++i) {19             ans = max(ans, abs(num[i - 1] - num[i]));20         }21         22         return ans;23     }24 private:25     int max(const int &x, const int &y) {26         return x > y ? x : y;27     }28     29     int abs(const int &x) {30         return x >= 0 ? x : -x;31     }32 };