Given 2 sorted arrays with distinct elements, one sorted in increasing order and other sorted in decreasing order. Can we find the element which is present in both of them in O(logN) or O((logN)2)?
Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 157 |
| 4 | maroonrk | 154 |
| 5 | -is-this-fft- | 148 |
| 5 | atcoder_official | 148 |
| 5 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | TheScrasse | 145 |
| 9 | nor | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.07.2024 10:22:41 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Good question. Personally I don't think it's possible but I have utterly no proof of my suspicion. I can only think of (trivial) O(NlogN) solution.
Yeah NlogN solution is clear
You can do O(N): just merge this two arrays and iterate over elements to see if there are equal neighbors.From this point of view it is clear that O(N) is the best complexity. For example, for arrays where elements of two arrays alternate when you merge them can be checked only through accessing all their elements by comparing all pairs.
Thanks!
We can use two pointers. Start from the left in one array and from the right in the other one (minimum element in each one). If the elements are equal, you've found a match. If not, move the pointer that has the minimum element.