Alternative linear space/time solution, recursive Radix sort in binary


  • 0
    Z

    This solution is quite not the optimal one, but also fits in linear space and time requirement. The idea is the same as in radix sort solution, but here I sorted the numbers by bits instead of decimal digits.

    public class Solution {
        List<Integer> sorted;
        public int maximumGap(int[] nums) {
            if(nums.length<2) return 0;
            System.out.println(nums.length);
            sorted =  new ArrayList<>(nums.length);
            for(int i = 0;i<nums.length;i++) sorted.add(nums[i]);
            bitSort(0, nums.length, new ArrayList<>(), new ArrayList<>(), 31);
            int max = 0;
            for(int i = 0;i<nums.length-1;i++) max = Integer.max(max, sorted.get(i+1)-sorted.get(i));
            return max;
        }
        
       
        
        public void bitSort(int s, int e,  List<Integer> left, List<Integer> right, int p){
           if(p<0 || e<=s) return;
           left.clear();
           right.clear();
           int x = (1<<p);
           for(int i = s;i<e;i++){
               int num = sorted.get(i);
               if((num&x) == 0) left.add(num);
               else right.add(num);
           }
           
           for(int i = s;i<s+left.size();i++){
               sorted.set(i, left.get(i-s));
           }
           for(int i = s+left.size();i<s+left.size()+right.size();i++){
               sorted.set(i, right.get(i-s-left.size()));
           }
           int leftSize = left.size(), rightSize = right.size();
           bitSort(s, s+leftSize, left, right, p-1);
           bitSort(s+leftSize, e,  left, right, p-1);
        } 
    }

Log in to reply
 

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