Java solution using quick sort


  • -2
    S
    public class Solution {
        public int maximumGap(int[] num) {
            if(num.length < 2){
                return 0;
            }
            qsort(0, num.length - 1, num);
            int maxDiff = 0;
            for(int i=1; i < num.length; i++){
                if(maxDiff < num[i] - num[i-1]){
                    maxDiff = num[i] - num[i-1];
                }
            }
            return maxDiff;
    
        }
        
        public void qsort(int l, int r, int[] num){
            if(l >= r){
                return;
            }
            
            int i, j, mid;
            mid = num[(l + r) / 2];
            i=l; j = r;
            while(i <= j){
                while(num[i] < mid) i++;
                while(num[j] > mid) j--;
                
                if(i <= j){
                    int temp;
                    temp = num[i];
                    num[i] = num[j];
                    num[j] = temp;
                    i++;j--;
                }
            }
            qsort(i, r, num);
            qsort(l, j, num);
        }
    }

  • 0
    C

    I don't think quicksort is linear.


  • 0
    S

    Thanks. You are right. I didn't notice that.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.