查找数组是否可以形成图形
Find if an array can form a graph
[面试题]最近在网上面试的时候遇到了这个问题。我不知道如何解决它。任何人都可以帮助我解决这个问题，以便我可以在 Java 中学习。
Tom 解决问题的能力很强。因此，为了测试汤姆的技能，杰瑞向汤姆提出了一道图形问题。 Jerry 给了 Tom，一个包含 N 个整数的数组 A。
一个图是一个简单的图，当且仅当它没有自环或多边。
现在 Jerry 问 Tom 他是否可以设计一个简单的 N 个顶点图。条件是 Tom 必须将 A 的每个元素恰好一次用于图的顶点度数。
现在，Tom 需要你的帮助来设计他的图表。如果图形可以设计则打印"YES"，否则打印"NO"（不带引号）。
输入
第一行一个整数T，表示测试用例的数量。
对于每个测试用例，有 2 行。
第一行是一个整数N，表示数组A的元素个数。
第二行有N-space个分隔的整数，代表A的元素。
输出
对于每个测试用例，在新行中打印 "YES" 或 "NO"（不带引号）图形是否可以设计。
约束条件
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
说明
对于第一个测试用例，我们可以设计一个简单的 3 个顶点的图，其度数序列为 [1, 2, 1]。第一个顶点的度数为 1，第二个顶点的度数为 2，第三个顶点的度数为 1。
对于第二个测试用例，我们无法制作一个简单的 3 个顶点的图，其度数序列为 [1, 1, 1].
一个必要条件是A中元素之和为偶数。这是由于每条边
在邻接列表中被计算两次。
接下来是尝试构建图，或至少 'allocate' 对节点。
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),
- 带有元素的排序部分，
- rest 也是排序的。
[面试题]最近在网上面试的时候遇到了这个问题。我不知道如何解决它。任何人都可以帮助我解决这个问题，以便我可以在 Java 中学习。
Tom 解决问题的能力很强。因此，为了测试汤姆的技能，杰瑞向汤姆提出了一道图形问题。 Jerry 给了 Tom，一个包含 N 个整数的数组 A。
一个图是一个简单的图，当且仅当它没有自环或多边。
现在 Jerry 问 Tom 他是否可以设计一个简单的 N 个顶点图。条件是 Tom 必须将 A 的每个元素恰好一次用于图的顶点度数。
现在，Tom 需要你的帮助来设计他的图表。如果图形可以设计则打印"YES"，否则打印"NO"（不带引号）。
输入 第一行一个整数T，表示测试用例的数量。 对于每个测试用例，有 2 行。 第一行是一个整数N，表示数组A的元素个数。 第二行有N-space个分隔的整数，代表A的元素。
输出 对于每个测试用例，在新行中打印 "YES" 或 "NO"（不带引号）图形是否可以设计。
约束条件
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
说明 对于第一个测试用例，我们可以设计一个简单的 3 个顶点的图，其度数序列为 [1, 2, 1]。第一个顶点的度数为 1，第二个顶点的度数为 2，第三个顶点的度数为 1。 对于第二个测试用例，我们无法制作一个简单的 3 个顶点的图，其度数序列为 [1, 1, 1].
一个必要条件是A中元素之和为偶数。这是由于每条边 在邻接列表中被计算两次。
接下来是尝试构建图，或至少 'allocate' 对节点。
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),
- 带有元素的排序部分，
- rest 也是排序的。