Code & Func

非常简单的一道题。。。为什么会出现在Medium中呢？

把G数组转成一个unordered_set就可以快速的判断某个元素是否在G中了，用一个flag来标识前一个元素是否在G中，初始值为false，然后遍历链表：

当前元素在G时，flag = true
当前元素不在G时，如果flag == true，计数就加一，然后flag = false。

遍历完链表后，再判断一次flag是否为真，如果是，则计数加一。

代码如下：

1
int numComponents(ListNode* head, vector<int>& G) {
2
  unordered_set<int> iset(G.begin(), G.end());
3
  int c = 0;
4
  bool flag = false;
5
  while (head)
6
  {
7
    if (iset.count(head->val) != 0) {
8
      flag = true;
9
    } else {
10
      c += flag;
11
      flag = false;
12
    }
13
        head = head->next;
14
  }
15
  c += flag;
2 collapsed lines
16
  return c;
17
}

时间复杂度为：O(n+m)
空间复杂度为：O(m)
n为链表大小，m为G的大小

当然如果不用unordered_set来做也是可以的，因为题目中限制了链表长度和值的范围，而G中元素都是链表中的元素，所以我们可以用一个长度为 10000 的数组来代替unordered_set。

代码如下：

1
int numComponents(ListNode* head, vector<int>& G) {
2
    // unordered_set<int> iset(G.begin(), G.end());
3
    vector<bool> iset(10000, false);
4
    for(int v: G) iset[v] = true;
5

6
    int c = 0;
7
    bool flag = false;
8
    while (head)
9
    {
10
        if (iset[head->val]) {
11
            flag = true;
12
        } else {
13
            c += flag;
14
            flag = false;
15
        }
5 collapsed lines
16
        head = head->next;
17
    }
18
    c += flag;
19
    return c;
20
}

时间复杂度为：O(n+m)
空间复杂度为：O(1)
n为链表大小，m为G的大小