[LeetCode]Find the Celebrity

这道题第一眼看上去可能没有太明确的思路，一般这种情况我们可以尝试从sub problem开始想。如果只有一个人a的话，a自己就是celebrity。如果再加一个人b，如果b知道a，显然b不可能是celebrity，a仍然有可能是。否则，如果a知道b，那么a肯定不是celebrity，而b有可能是，我们就把b选为可能的候选。同理，加上第三个人c之后我们也可以决定是b仍然可能还是c替换b。那么这样我们可以不断地从n - 1的scale推理到n的scale。最后我们会有一个候选者，其他人都被排除了可能，我们还需要验证这个候选者是不是真正的celebrity，这个步骤线性时间就可以完成。时间复杂度O(n)，常数空间，代码如下：

	// Forward declaration of the knows API.
	bool knows(int a, int b);
	class Solution {
	public:
	int findCelebrity(int n) {
	if(n < 1)return -1;
	int candidate = 0;
	for(int i = 1; i < n; ++i)
	{
	if(!knows(i, candidate))
	candidate = i;
	}
	//double check if candidate is celebrity
	for(int i = 0; i < n; ++i)
	{
	if(i == candidate)continue;
	if(!knows(i, candidate) || knows(candidate, i))
	return -1;
	}
	return candidate;
	}
	};

view raw Find the Celebrity.cpp hosted with ❤ by GitHub