java ac solution


  • 0
    Z
     public int findCelebrity(int n) {
            // hashmap(person A, all those people who know A)
            HashMap<Integer,List<Integer>> map = new HashMap<>();
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(j != i){
                        if(knows(j,i)){
                            if(map.containsKey(i)){
                                List<Integer> ls = map.get(i);
                                ls.add(j);
                                map.put(i,ls);
                            }else{
                                List<Integer> ls = new ArrayList<Integer>();
                                ls.add(j);
                                map.put(i,ls);
                            }
                        }
                    }
                }
            }
            // if a person is known by all others, check if he doesn't know anyone
            for(int i : map.keySet()){
                if(map.get(i).size() == n-1){
                    for(int j=0;j<n;j++){
                        if(j != i){
                            if(knows(i,j)){
                                break;
                            }else{
                                if((i==n-1 && j== n-2) || j == n-1)return i;
                            }
                        }
                    }
                }
            }
            return -1;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.