Есть такое задание: Given an array with 100 elements (numbers

Question

Есть такое задание: Given an array with 100 elements (numbers

from 0 to 99). One element has been removed from the array. How would you find the removed element? How would you solve this if the array is sorted, or the array is not sorted?

Для остортированного массива написал такую версию быстрого поиска:
int findRemovedInSequence(const vector<int>& v) {
int left = 0;
int right = v.size() + 1;
auto getIndex = [&] { return (left+right)/2; };
int index = getIndex();

while (true) {
if (v.size() == index) {
return v.size();
}
if (0 == index ||
v.at(index) != index && v.at(index - 1) == index - 1) {
return index;
}
else if (v.at(index) == index) { //search in right subseq
left = index;
index = getIndex();
}
else if (v.at(index) != index) { //search in left subseq
right = index;
index = getIndex();

}
}
}

Вопросы:
1. Правильно ли я понимаю, что здесь сложность O(n*logn)?
2. Можно ли оптимизировать еще?
3. Есть ли какой нормальный вариант для неотсортированного варианта, кроме отсортировать перед поиском? И что будет в таком случае, если qsort тоже n*logn? 2*n*logn?

#c #embedded #programming #russian

0

24.10.2018

1 ответов

9 просмотров

Constantine Drozdov · Accepted Answer

Constantine Drozdov

Я не понял задачу. Удален без переупорядочивания?

0

24.10.2018

170 похожих чатов

Есть такое задание: Given an array with 100 elements (numbers

1 ответов

Похожие вопросы