4ms C++ solution based on binary search


  • 0
    G
    class Solution {
    public:
    	string Parse(int d)
    	{
    		char buf[30] = {0};
    		sprintf(buf, "%d",d);
    		string ret(buf);
    		return ret;
    	}
    
    	string Parse(int d1, int d2)
    	{
    		char buf[30] = {0};
    		sprintf(buf, "%d", d1);
    		string tmp(buf);
    		memset(buf, 0, 30);
    		tmp.append("->");
    		sprintf(buf, "%d", d2);
    		string tmp2(buf);
    		tmp.append(tmp2);
    		return tmp;
    	}
    
    	int findSection(int A[], int n, int v)
    	{
    		int start = 0;
    		int end = n - 1;
    	
    		if(n<=0) return -1;
    
    		while (1)
    		{
    
    			int m = (start + end) / 2;
    
    			if (A[m] == v) return m;
    
    			if (v<A[m])
    			{
    				if (m == 0) return 0;
    				if (v > A[m - 1]) return m;
    				else end = m - 1;
    			}
    
    			if (v>A[m])
    			{
    				if (m == n - 1) return n - 1;
    				if (v<A[m + 1]) return m + 1;
    				start = m + 1;
    			}
    		}
    	}
    
    	vector<string> findMissingRanges(int A[], int n, int lower, int upper)
    	{
    		int p = findSection(A, n, lower);
    		int q = findSection(A, n, upper);
        
    		vector<string> ret;
    		char buf[30] = {0};
    	
    		if(p==-1)
    		{
    			if(upper==lower)
    			{
    				ret.push_back(Parse(lower));
    				return ret;
    			}
    			else
    			{
    				ret.push_back(Parse(lower, upper));
    				return ret;
    			}
    		}
    
    		if (p > q) return ret;
    		int i = p;
    
    		if (A[p] - lower>0)
    		{
    			if (A[p] - lower == 1)
    			{
    				ret.push_back(Parse(lower));
    			}
    			else
    			{
    				ret.push_back(Parse(lower, A[p]-1));	
    			}
    		}
    
    		i++;
    		while (i<=q)
    		{
    			if (A[i] - A[i-1]>1)
    			{
    				if (A[i] - A[i - 1] == 2)
    				{
    					ret.push_back(Parse(A[i - 1] + 1));
    				}
    				else
    				{
    					ret.push_back(Parse(A[i - 1] + 1, A[i]-1));
    				}
    			}
    
    			i++;
    		}
    
    		if (upper-A[q]>0)
    		{
    			if (upper - A[q] == 1)
    			{
    				ret.push_back(Parse(upper));
    			}
    			else
    			{
    				ret.push_back(Parse(A[q] + 1, upper));
    			}
    		}
    
    		return ret;
    	}
    };

Log in to reply
 

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