LeetCode 277 Find the Celebrity

LeetCode 277 Find the Celebrity

Link: leetcode.com/problems/fi…

Solution: Be greedy

Time complexity: O(n), no more than 3N calls to knows(a,b)

Space complexity: O(n)

Idea: Set res to 0 at the beginning and then go all the way through. As long as res knows(res, I), it means res knows I and res can no longer be a celebrity, so set res to I. Finally, scan all of res to see if there is any behavior that violates celebrity standards. What is the right thing to do, i.e., why is the possible result RES obtained in this way, so that res is the only one of all people who could be a celebrity? You’re not gonna miss anything?

For example, when “knows” (res, I) is true, it means that Res can no longer be a celebrity because res knows someone else. Those elements between res and I, res is not set to those, so RES doesn’t know those people, so those people can’t be celebrities. So from Res to I, only I can be a celebrity. In the beginning we set res to 0, as you can imagine, assuming that the middle knows(0,3) is true, which means that 1 and 2 are definitely not Celerity, we set RES to 3 and continue running, and then somewhere else we say knows(3,7) is true, which means that 456 is not a celebrity. Set to 7… In this way, the simulation will find that there are no considerations in such a scan. In the end, whoever Res is will be the only person who can be a Celebrity.

Code:

/* The knows API is defined in the parent class Relation. boolean knows(int a, int b); * /

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int res = 0;
        for (int i = 1; i < n; i++) {
            if(knows(res, i)) { res = i; }}for (int i = 0; i < n; i++) {
            if(res ! = i && (knows(res, i) || ! knows(i, res))) {return -1; }}returnres; }}Copy the code