java - 判断一个数组是否可以形成一个图

Question

[面试问题]我在最近的一次在线面试中遇到了这个问题。我不知道如何解决它。谁能帮我解决这个问题，以便我可以学习Java。

汤姆非常擅长解决问题。为了测试汤姆的技能，杰瑞向汤姆提出了一个图形问题。 Jerry 给 Tom 一个包含 N 个整数的数组 A。

图是一个简单图，当且仅当它没有自环或多边。

现在杰瑞问汤姆是否可以设计一个包含 N 个顶点的简单图。条件是 Tom 必须使用 A 中的每个元素一次来计算图的顶点度数。

现在，汤姆需要您的帮助来设计他的图表。如果可以设计图形，则打印“YES”，否则打印“NO”(不带引号)。

输入 第一行单个整数 T，表示测试用例的数量。 对于每个测试用例，有 2 行。 第一行是一个整数N，表示数组A的元素数量。 第二行有 N 个空格分隔的整数，代表 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]。

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)，
• 使用元素排序部分，
• 其余部分也已排序。