自己的做法
算法思想
首先遍历列表G，将整型值放入set集合中。
设置结果变量res，初始为0。然后遍历链表，设置一个标记值flag，用来标记当前节点之前一段的节点是否都在集合中。
即如果当前节点值在集合中，判断flag，如果flag = false，则res + 1，并将flag 设为true；如果flag = true，则不做任何操作。
如果当前节点不在集合中，则将flag 设为false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int numComponents(ListNode* head, vector<int>& nums) {
set<int> s;
for(int i = 0; i < nums.size(); i++) {
s.insert(nums[i]);
}
ListNode * cur = head;
int res = 0;
bool flag = false;
while (cur) {
if(s.count(cur->val)) {
if(!flag) {
res++;
flag = true;
}
} else {
flag = false;
}
cur = cur->next;
}
return res;
}
};
|
性能分析
列表G的长度为a，链表长度为b
时间复杂度：为O(a+b)。
空间复杂度：O(a)。
参考做法
算法思想
同样是先讲列表G中元素添加到set集合中。
然后对链表进行依次扫描(就是遍历)，一个组件在链表中对应一段连续节点，那么如果当前节点在列表G中，且下一个节点不在列表G中，那么就找到了一个组件的尾节点，res加1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int numComponents(ListNode* head, vector<int>& nums) {
set<int> s;
for(int i = 0; i < nums.size(); i++) {
s.insert(nums[i]);
}
ListNode * cur = head;
int res = 0;
while (cur) {
if(s.count(cur->val) && (cur->next == nullptr || s.count(cur->next->val))) {
res++;
}
cur = cur->next;
}
return res;
}
};
|
性能分析
同上。