Find the longest consecutive subsequence in an unsorted array.
To be honest, I could not solve this problem in O(n) complexity on my own.
I understood the approach only after reading someone else’s code.
I had thought about using a hash, but I recalled that STL’s map has O(log n) lookup complexity, which would result in an overall O(n log n) complexity, so I gave up on that idea.
Today I took the time to properly understand what hash tables are, and the differences between map, set, hash_map, and hash_set. It was quite helpful.
I also learned about a library called Boost, which is a quasi-standard C++ library. Feel free to look it up if you are interested.
The final solution for this problem is hash + left-right expansion simulation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
ListNode * GetListNthNode(ListNode * head, int n) {
int k = 0;
while(k < n) {
k++;
head = head->next;
}
return head;
}
int CountList(ListNode *head) {
int count = -1;
while(head != NULL) {
head = head->next;
count++;
}
return count;
}
TreeNode *BSearchT(int left, int right, ListNode * head) {
if(right < left) return NULL;
int mid = (left + right) / 2;
TreeNode * root = new TreeNode(GetListNthNode(head, mid - left)->val);
root->left = BSearchT(left, mid - 1, head);
root->right = BSearchT(mid + 1, right, GetListNthNode(head, mid + 1 - left));
return root;
}
TreeNode *sortedListToBST(ListNode *head) {
if(head == NULL)
return NULL;
int n = CountList(head);
int mid = (0 + n) / 2;
TreeNode * root = new TreeNode(GetListNthNode(head, mid)->val);
root->left = BSearchT(0, mid - 1, head);
root->right = BSearchT(mid + 1, n, GetListNthNode(head, mid + 1));
return root;
}
};
|