Блог пользователя harrypotter0

Автор harrypotter0, история, 7 лет назад, По-английски

Given an int array which might contain duplicates, find the largest subset of it which form a sequence. Ex: {1,6,10,4,7,9,5} then ans is 4,5,6,7

Sorting is an obvious solution. Can this be done in O(n) time ??

Thanks in advance :)

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have a simple idea, but I am not sure whether this is correct or not.

We can adopt a "hash table" to record the integers that have appeared in the set, i.e., for some integer N, if it appears in the set, then hash[N] = 1; otherwise hash[N] = 0. Then, the problem is equivalent to finding out the longest sub-sequence consisting of "1"s. If I were correct, this solution has complexity O(n). However, this approach fails if the maximum integer turns out to be too large, for instance, 109.

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +15 Проголосовать: не нравится

On the one hand, using a hash table, we can dfs/bfs and find connected components on the path graph (add an edge for each adjacent elements) to solve the problem in Θ(n) expected time.

On the other hand, on the algebraic decision tree model, your problem cannot be solved in O(n) time. To see this, take an instance of the set disjointness problem (A, B) and transform it to [3A1, ..., 3An, 3B1 + 1, ..., 3Bn + 1]. Because the set disjointness problem has lower bound [1], your problem has the same bound.