277. Find the Celebrity

• 277. Find the Celebrity
  • Description
  • Pitfall
  • Solution

Description

Here

Pitfall

正常解法

    public int findCelebrity(int n) {
      int candidate = 0;
      for (int i = 1; i < n; i++) {
        if (knows(candidate, i)) {
          candidate = i;
        }
      }

      for (int i = 0; i < n; i++) {
        if (i != candidate && (!knows(i, candidate) || knows(candidate, i))) {
          return -1; // no celebrity
        }
      }

      return candidate;
    }

其实第二个loop还有个优化

public int findCelebrity(int n) {
      int candidate = 0;
      // find the candidate
      for (int i = 1; i < n; ++i) {
        if (knows(candidate, i)) candidate = i;
      }
      // make sure it's a valid celebrity
      for (int i = candidate + 1; i < n; i++) {
        if (!knows(i, candidate)) {
          return -1;
        }
      }

      for (int i = 0; i < candidate; i++) {
        if (knows(candidate, i)) {
          return -1;
        }
      }

      return candidate;
    }

Solution