Найти, если массив может сформировать график

Question

[Интервью Вопрос] Я получил этот вопрос в недавнем онлайн-интервью. Я не знал, как его решить. Может кто-нибудь, пожалуйста, помогите мне решить это, чтобы я мог учиться на Java.

Том очень хорош в решении проблем. Поэтому, чтобы проверить навыки Тома, Джерри спрашивает Тома о графике. Джерри дает Тому, массив A из N целых чисел.

Граф - простой граф, если он не имеет самопересечений или многогранников.

Теперь Джерри спрашивает Тома, может ли он составить простой граф из N вершин или нет. Условие заключается в том, что Том должен использовать каждый элемент A ровно один раз для степеней вершин графа.

Теперь Том хочет, чтобы ваша помощь составляла его график. Распечатайте «ДА», если график можно создать, иначе напечатайте «НЕТ» (без кавычек).

Ввод Одно целое число T в первой строке, обозначающее количество тестовых случаев. Для каждого тестового примера есть 2 строки. Первая строка представляет собой одно целое число N, обозначающее количество элементов массива A. Вторая строка имеет N-пространство, отделенное целые числа, представляющие элементы А.

Выходные Для каждого теста печати «ДА» или «НЕТ» (без кавычек), может ли график быть сконструирован или нет, в новой строке.

Ограничения

1<= T <= 100 
1<= N <= 100 
0<= Element of A <= 5000 

Образец теста Случаи

Входные

1 
2 
1 1 

Выход

YES 

Объяснение Для этого теста, простой граф с 2 вершинами могут быть разработаны, где каждая вершина имеет степень 1.

Входной

2 
3 
1 2 1 
3 
1 1 1 

Выход

YES 
NO 

Объяснение Для первого теста, мы можем разработать простой граф из трех вершин, имеющий последовательность степеней как [1, 2, 1]. Первая вершина имеет степень 1, вторая, имеет 2 и третью 1. Для второго тестового примера мы не можем составить простой граф из трех вершин, имеющий последовательность степеней как [1, 1, 1].

Answer 1

Состояние одной вещи есть, что сумма элементов в A равно. Это связано с тем, что каждое ребро засчитывается дважды в списке смежности.

Далее следует попытаться построить граф или по крайней мере «выделить» пары узлов.

Sort elements of A in decending order, 
Let the largest (first) element be a, 
Check are element on positions 2 to a+1 larger than 0, 
    If there is a element with value 0 than it is not possible to construct a graph, 
Decrease these a elements by 1 and set first element to 0, 
Repeat process until all elements are 0. 

Обратите внимание, что сортировка на последующих этапах может быть сделано в O (N) с шагом сортировки слиянием, поскольку список состоит из трех отсортированных частей:

• первый элемент (0), который может пойти в конец,
• сортированная деталь с элементами,
• отдых, который также сортируется.