AC java solution, Radix sort to sort in linear time O(32*n)


  • 0
    R

    For Simplicity I will use 4 bits to explain.
    if we have {-6,-3,-5,1,2}

    For 4 bits, the most significant bit will be used for sign. So binary representation will be

    -6 -> 1010

    -3 -> 1101

    -5 -> 1011

    1 -> 0001

    2 -> 0010

    we will create a map with keys 0,1 Mapping to LinkedList


    [0] ->

    [1] ->

    looking bits from right

    -6 -> 101 0

    -3 -> 110 1

    -5 -> 101 1

    1 -> 000 1

    2 -> 001 0

    using the bits to map to respective key.

    [0] -> -6 -> 2

    [1] -> -3 -> -5 ->1

    put them back into the array

    -6 , 2 , -3 , -5 , 1

    checking the next bits

    -6 -> 10 1 0

    2 -> 00 1 0

    -3 -> 11 0 1

    -5 -> 10 1 1

    1 -> 00 0 1

    using the bits to map to respective key.

    [0] -> -3 -> 1

    [1] -> -6 -> 2 ->-5

    put them back into the array

    -3 , 1 , -6 , 2 , -5

    checking the next bits

    -3 -> 1 1 0 1

    1 -> 0 0 0 1

    -6 -> 1 0 1 0

    2 -> 0 0 1 0

    -5 -> 1 0 1 1

    using the bits to map to respective key.

    [0] -> 1 -> -6-> 2 ->-5

    [1] -> -3

    put them back into the array

    1,-6,2,-5,-3

    The most significant bit is sign, we have to use it to bring all the negative integers before the positive. so if the most significant bit is 1 we map to 0 and vice-versa.

    1 -> 0 0 0 1

    -6 -> 1 0 1 0

    2 -> 0 0 1 0

    -5 -> 1 0 1 1

    -3 -> 1 1 0 1

    [0] -> -6 -> -5 -> -3

    [1] -> 1 -> 2 ->

    put them back into the array

    -6, -5, -3, 1, 2

    We have the array sorted in linear time, from here its one more loop to check for a sequence.

    public int longestConsecutive(int[] nums) {
            HashMap<Integer,LinkedList<Integer>> hm = new HashMap<Integer,LinkedList<Integer>>();
    		hm.put(0,new LinkedList<Integer>());
    		hm.put(1,new LinkedList<Integer>());
    		for(int i=0;i<32;i++){
    			for(int j=0;j<nums.length;j++){
    				if(i!=31){
    					int k = (nums[j]>>>i) & 1;
    					hm.get(k).add(nums[j]);
    				}
    				else{
    					int k = ((nums[j]>>>i) & 1 )^1;
    						hm.get(k).add(nums[j]);
    				}
    			}
    			Iterator itr = hm.entrySet().iterator();
    			int k=0;
    			while (itr.hasNext()) {
    				Map.Entry<Integer,LinkedList<Integer>> lst = (Map.Entry)itr.next();
    				while(!lst.getValue().isEmpty()){
    					nums[k]=lst.getValue().pop();
    					k++;
    				}
    			}
    			hm = new HashMap<Integer,LinkedList<Integer>>();
    			hm.put(0,new LinkedList<Integer>());
    			hm.put(1,new LinkedList<Integer>());
    		}
    		int max=1;
    		int curr=1;
    		for(int i =0;i<nums.length-1;i++){
    			if(nums[i]==nums[i+1]){
    				continue;
    			}
    			if(nums[i]+1==nums[i+1]){
    				curr=curr+1;
    				max=Math.max(max,curr);
    			}
    			else{
    				curr=1;
    			}
    		}
    		return max;
        }

Log in to reply
 

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