We are given head
, the head node of a linked list containing unique integer values.
We are also given the list G
, a subset of the values in the linked list.
Return the number of connected components in G
, where two values are connected if they appear consecutively in the linked list.
Input:
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation:
0 and 1 are connected, so [0, 1] and [3] are the two connected components.
Input:
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation:
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.
- If
N
is the length of the linked list given by head,1 <= N <= 10000
. - The value of each node in the linked list will be in the range
[0, N - 1]
. 1 <= G.length <= 10000
.G
is a subset of all values in the linked list.
- Java
-
mine
Runtime: 156 ms, faster than 5.08%, Memory Usage: 49.3 MB, less than 7.69% of Java online submissions
public int numComponents(ListNode head, int[] G) { if (G.length == 1) { return 1; } int count = 0; int t = 0; while (head != null) { boolean c = contain(G, head.val); if (c) { t++; } else { count += (t == 0 ? 0 : 1); t = 0; } head = head.next; } if (t != 0) { count++; } return count; } public boolean contain(int[] G, int v) { for (int t : G) { if (t == v) { return true; } } return false; }
-
the most votes
Runtime: 6 ms, faster than 49.38%,Memory Usage: 40.5 MB, less than 76.92% of Java online submissions
public int numComponents(ListNode head, int[] G) { Set<Integer> setG = new HashSet<>(); for (int i: G) setG.add(i); int res = 0; while (head != null) { if (setG.contains(head.val) && (head.next == null || !setG.contains(head.next.val))) res++; head = head.next; } return res; }
-