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

Finding an O(n) time algo.
Автор acc1, 16 лет назад, По-английски
Given Two arrays of n numbers. Find Whether they are disjoint or not.

Each Element lie in range [0,n^100] .

Space : O(n)

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

16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
If you mean expected O(n) then this is just a hash-table problem.
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Looks like a hash-related problem, but not sure about n^100!
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
You can unify these arrays to one and sort it by radix sort. Then you can find two adjanced equal items in large array, which were in different arrays. If you can find this, arrays aren't disjoint.

Sorry for bad English...
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится
Hash - Table ..mmm..but it is implemented using rb tree, then how come O(n) ? , then it will get O(n*lgn) ....

Answer above question, and one more thing , can we do this using bitwise kung-fu , like Xoring (just a guess) .
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
How about using a set? Store all the numbers of the first array in a set. A set only requires O(log(n)) time for instertion and search. And it also requires O(n) memory AFAIK.
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится
Size of input in this problem is O(n * log(n100)) = O(nlog(n)) so it can't be solved in O(n) time. At least unless we have some special agreements about working with long numbers in O(1) time.
→ Ответить