Проблема

In a town, there are N people labelled from 1 to N.  There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.
If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return -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

Пример 4:

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

Пример 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

Ограничения:

  • 1 <= N <= 1000
  • 0 <= trust.length <= 10^4
  • trust[i].length == 2
  • trust[i] все разные
  • trust[i][0] != trust[i][1]
  • 1 <= trust[i][0], trust[i][1] <= N

Решение

Входными данными являются N как целое число и trust как двумерный массив.

Чтобы лучше понять отношения между городским судьей и всеми, мы можем привести пример:

Пример 1:

1 имеет одностороннее соединение с 2, а 2 не имеет связи с другими. 2 никому не доверяет, а все остальные доверяют 2, поэтому 2 - городской судья. Это ориентированный граф.

Пример 2:

1 и 2 оба имеют одностороннее соединение с 3, а 3 не имеет исходящего указателя, подключенного к другим. Таким образом, 3 судьи города.

Пример 3:

2 имеет одностороннее соединение с 3, но 1 и 3 имеют двустороннее соединение. Нет элемента, который никому не доверяет, поэтому мы возвращаем -1.

Чтобы упростить понимание, мы можем сказать, что пытаемся найти элемент, который никого не любит, но нравится людям N-1 в городе. Как мы можем отслеживать, сколько раз понравился элемент? Мы используем хеш.

Чтобы рассчитать два разных количества лайков и лайков, мы устанавливаем ключи хешей от 1 до N, чтобы мы не пропустили ни одного числа. И мы перебираем массив доверия, чтобы увеличить количество лайков и лайков в соответствии с порядком элементов подмассива. Код выглядит следующим образом.

Общая временная сложность - O (n), а пространственная сложность - O (n).

Надеюсь, это даст вам несколько идей о том, как решить подобную проблему.

Ресурсы:



Найдите городского судью - LeetCode
В городе N человек, помеченных от 1 до N. Ходят слухи, что один из этих людей тайно принадлежит к городу… leetcode.com





График в JavaScript
Основы работы с графиком medium.com