力扣labuladong一刷day43天名人问题

2023-12-21 23:31:50

力扣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;
    }
}

文章来源:https://blog.csdn.net/qq_43511039/article/details/135122887
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。