Finden Sie, ob ein Array ein Diagramm bilden kann

Question

[Interview Frage] Ich habe diese Frage in einem kürzlich online-Interview. Ich hatte keine Ahnung, wie ich es lösen sollte. Kann mir bitte jemand helfen, das zu lösen, damit ich in Java lernen kann.

Tom ist sehr gut in der Problemlösung. Um Toms Fähigkeiten zu testen, fragt Jerry Tom ein Graphenproblem. Jerry gibt Tom ein Array A von N ganzen Zahlen.

Ein Graph ist ein einfacher Graph, wenn er keine Selbstschleife oder Multikanten hat.

Jetzt fragt Jerry Tom, ob er einen einfachen Graphen von N Knoten erstellen kann oder nicht. Bedingung ist, dass Tom jedes Element von A genau einmal für die Scheitelpunkte des Graphen verwenden muss.

Nun möchte Tom Ihre Hilfe bei der Gestaltung seines Graphen. Drucken Sie "YES", wenn das Diagramm entworfen werden kann, andernfalls "NO" (ohne Anführungszeichen).

Eingabe Eine einzelne Zahl T in der ersten Zeile, die die Anzahl der Testfälle angibt. Für jeden Testfall gibt es 2 Zeilen. Die erste Linie eine einzige ganze Zahl N ist, bezeichnet die Anzahl der Elemente der Arrays A Die zweite Zeile weist N-Raum getrennt ganze Zahlen, die Elemente von A. repräsentierte

Output für jeden Testfall, print „JA“ oder "NO" (ohne Anführungszeichen), ob der Graph in einer neuen Zeile entworfen werden kann oder nicht.

Constraints

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

Beispieltestfälle

Eingang

1 
2 
1 1 

Ausgabe

YES 

Erklärung Für diesen Testfall, ein einfacher Graph mit 2 Vertices kann so gestaltet werden, wobei jeder Eckpunkt Grad 1.

Eingang

2 
3 
1 2 1 
3 
1 1 1 

Output

YES 
NO 

Erläuterung Für den ersten Testfall hat, können wir ein einfaches Design Graph von 3 Vertices, der eine Gradfolge wie [1, 2, 1] hat. Der erste Vertex hat Grad 1, der zweite hat 2 und der dritte hat 1. Für den zweiten Testfall können wir keinen einfachen Graphen von 3 Vertices machen, der eine Gradfolge wie [1, 1, 1] hat.

Answer 1

Eine notwendige Bedingung ist, dass die Summe der Elemente in A gerade ist. Das liegt daran, dass jede Kante in der Adjuencenzliste doppelt gezählt wird.

Als nächstes wird versucht, ein Diagramm zu konstruieren oder Knotenpaare zu "allozieren".

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. 

anzumerken, dass in der nachfolgenden Schritten Sortieren kann in O (n) mit merge Sortierschritt erfolgen, da der Liste von drei sortierten Teilen besteht:

• erstes Element (0), die gehen können das Ende,
• sortierten Teil mit Elementen,
• Rest, der auch sortiert ist.