Defeat 95% Java, AC new Hash solution (no-sort!!!)


  • 0
    T

    using hash array to record the entry status:
    use -1, 0, 1, 2 to mark the status:
    0: not in any intervals
    -1: in the interval that end=start, e.g. [1,1]
    1: the entries (except for end entry) of any interval that end!=start
    e.g. for [1,3]:
    hash[1] and hash[2] are in status 1.
    2: the end of any interval that end!=start
    e.g. for [1,3]:
    hash[3] is in status 2.

    Caution:
    priority: 1>2>-1>0.
    please try to understand it by your own!

    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            int MAX = -1;
            for(int i=0; i<intervals.size(); i++) { // get maxmium entry
                if(intervals.get(i).end > MAX) MAX = intervals.get(i).end;
            }
            //using hash array
            int[] hash = new int[MAX+2];
            for(int i=0; i<intervals.size(); i++) {
            	if(intervals.get(i).start == intervals.get(i).end) {
            		if(hash[intervals.get(i).start] == 0) //do not disturb other intervals
            			hash[intervals.get(i).start] = -1;
            	}
            	else {
    	            for(int j=intervals.get(i).start; j<intervals.get(i).end; j++) {
    	            	//from start to end
    	                hash[j] = 1;
    	            }
            		//we have to make sure [1,3] [4,6] can not be merged
            		// we have to also make sure this will not end up the previous continuous intervals
            		if(hash[intervals.get(i).end] != 1) 
            			hash[intervals.get(i).end] = 2; //end sign
            	}
            }
            //traverse to get merged section
            List<Interval> result = new ArrayList<Interval>();
            int s = -1;
            for(int i=0; i<=MAX+1; i++) {
            	if(hash[i] == -1) { // self-interval
            		result.add(new Interval(i, i));
            	}
            	else if(hash[i] == 1 && s == -1) { // new interval
            		s = i;
            	}
                else if(hash[i] == 2 && s!=-1) { // interval is end
                    result.add(new Interval(s, i));
                    s=-1;
                }
            }
            return result;
        }
    }
    

  • 0
    T

    this solution is great and not using any sort functions!


Log in to reply
 

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