리트코드 #997. 마을 판사 찾기

반응형

마을에는 1부터 n까지 표시된 사람이 n명 있습니다. 이 중 한 명이 비밀리에 마을 판사라는 소문이 있다.

마을 판사가 존재할 경우:

• 마을 판사는 아무도 믿지 않는다.
• 마을 판사를 제외한 모든 사람이 마을 판사를 신뢰한다.
• 성질 1과 2를 만족하는 사람이 딱 한 명 있습니다.

ai로 분류된 사람이 bi로 분류된 사람을 신뢰한다는 것을 나타내는 신뢰[i] = [ai, bi]가 배열 트러스트가 주어진다.

 

마을 판사가 존재하여 신원을 확인할 수 있는 경우 마을 판사의 레이블을 반환하고 그렇지 않은 경우 -1을 반환한다.

예 1:

Input: n = 2, trust = [[1,2]]
Output: 2

예 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

 

예 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

해결책:

브루트 포스 접근 방식:

모든 사람이 그를 신뢰하고 그는 아무도 신뢰하지 않는지 n번 확인할 때마다, 만약 누군가가 발견되면 다른 사람은 -1을 반환한다.

 

시간 복잡성: O(n*m), 여기서 m은 신뢰 배열의 행 수입니다.

공간 복잡성: O(1). 추가 공간이 사용되지 않습니다.

최적화:

왜냐하면 만약 우리가 누군가를 믿었던 횟수 혹은 그가 믿었던 횟수를 셀 수 있다면.

따라서 FirstSide(그가 신뢰한 )와 SecondSide(신뢰한 사람)의 두 배열을 선택합니다. 임의의 숫자에 대해 FirstSide가 0이면 아무도 신뢰하지 않고 SecondSide가 n-1이면 n-1의 신뢰를 받는다는 의미이고, 아무도 반환 -1을 찾지 못한 경우 심판입니다.

 

코드를 보자 -

시간 복잡성: O(n)

공간 복잡성: O(n)

결론:

 

2022년 1월 3일 문제: Leetcode의 오늘의 문제. 이와 같이 더 많은 업데이트를 원하면 팔로우하십시오.

솔루션 수정에 대한 여러분의 소중한 생각이나 제안을 언급합니다.