A divide and conquer solution


  • 1
    G
    // Forward declaration of the knows API.
    bool knows(int a, int b);
    
    class Solution {
    public:
    	int findCelebrity(int n) 
    	{
    		if (n <= 1) return -1;
    		return find(0,n-1);
    	}
    
    	int find(int s, int e)
    	{
    		if (s >= e) return s;
    
    		int m = (s + e) / 2;
    		int r1 = find(s, m);
    		int r2 = find(m + 1, e);
    
    		if (r1 < 0 && r2 < 0) return -1;
    
    		int t1 = r1;
    		if (r1 >= 0)
    		{
    			for (int k = m + 1; k <= e; k++)
    			{
    				if (!knows(k, r1) || knows(r1, k))
    				{
    					t1 = -1;
    					break;
    				}
    			}
    		}
    
    		int t2 = r2;
    		if (r2 >= 0)
    		{
    			for (int k = s; k <= m; k++)
    			{
    				if (!knows(k, r2) || knows(r2, k))
    				{
    					t2 = -1;
    					break;
    				};
    			}
    		}
    
    		return t1 >= 0 ? t1 : t2;
    	}
    };

Log in to reply
 

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