817. Linked List Components

LeetCode
,

今天的题目是817. Linked List Components。

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

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

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

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int numComponents(ListNode* head, vector<int>& G) {
	unordered_set<int> iset(G.begin(), G.end());
	int c = 0;
	bool flag = false;
	while (head)
	{
		if (iset.count(head->val) != 0) {
			flag = true;
		} else {
			c += flag;
			flag = false;
		}
		    head = head->next;
	}
	c += flag;
	return c;
}
  • 时间复杂度为：O(n+m)
  • 空间复杂度为：O(m)
  • n为链表大小，m为G的大小

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int numComponents(ListNode* head, vector<int>& G) {
    // unordered_set<int> iset(G.begin(), G.end());
    vector<bool> iset(10000, false);
    for(int v: G) iset[v] = true;

    int c = 0;
    bool flag = false;
    while (head)
    {
        if (iset[head->val]) {
            flag = true;
        } else {
            c += flag;
            flag = false;
        }
        head = head->next;
    }
    c += flag;
    return c;
}
  • 时间复杂度为：O(n+m)
  • 空间复杂度为：O(1)
  • n为链表大小，m为G的大小