Bucket sort O(N) , 100% performance


  • 0

    /**

    • Definition for an interval.
    • public class Interval {
    • int start;
      
    • int end;
      
    • Interval() { start = 0; end = 0; }
      
    • Interval(int s, int e) { start = s; end = e; }
      
    • }
      */
    public class Solution {
        public int[] findRightInterval(Interval[] intervals) {
            int minStart=Integer.MAX_VALUE;
            int maxStart=Integer.MIN_VALUE;
            for(int i=0;i<intervals.length;i++)
            {
                minStart=Math.min(intervals[i].start,minStart);
                maxStart=Math.max(intervals[i].start,maxStart);
            }
            int[] ret = new int[intervals.length];
           List<Integer> arr = new ArrayList<Integer>(maxStart-minStart+1);
           for(int i =0;i<maxStart-minStart+1;i++) arr.add(null);
            for(int i=0;i<intervals.length;i++)
             arr.set(intervals[i].start-minStart,i);
            for(int i=0;i<ret.length;i++)
            {
                int j=intervals[i].end-minStart;
                while( j<arr.size()&& arr.get(j)==null) j++;
                if(j>=arr.size()) 
                {
                    ret[i]=-1;
                }
                else{
                    ret[i]=arr.get(j);
                }
            }
            return ret;
        }
    }
    

  • 0
    H

    It's good, but have you considered such case [[1,2],[20000000,20000001]]? Bucket sort will waste much more memory and be much slower than normal O(nlogn) algorithm.

    for(int i =0;i<maxStart-minStart+1;i++) arr.add(null);
    

Log in to reply
 

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