力扣labuladong一刷day43天名人问题

力扣labuladong一刷day43天名人问题

一、277. 搜寻名人

题目链接：https://leetcode.cn/problems/find-the-celebrity/
思路：无不认识其他人，其他人都认识我，这就是名人，想o(n)，可以从头开始两人两个人的排除一个，所有人为一个list，每次开头的两个，如果a一定不是名人就把b加进去，否则就把b保留，这样只需要O(n)就排除的只剩下一个人了，然后再具体看她。

public class Solution extends Relation {
    public int findCelebrity(int n) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }

        while (list.size() >= 2){
            Integer a = list.removeFirst();
            Integer b = list.removeFirst();
            if (knows(a, b) || !knows(b, a)) {
                list.addFirst(b);
            }else {
                list.addFirst(a);
            }
        }
        Integer i = list.removeFirst();
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (knows(i, j) || !knows(j, i)) return -1;
        }
        return i;
    }
}