Нахождение наибольшего числа в массиве меньше или равно цели
Это то, что я делаю.
У меня есть массив (или вектор), V, а затем я сортирую его в порядке возрастания.
Наибольшее число меньше или равно цели a будет в положении i.(первоначально, i = 0)
while (V[i] <= a && i < V.size()) { i++; }
i--;
Я использую эту часть кода в вопросе о Codechef и получаю AC, однако раньше я использовал это и получал это неправильно.
while (V[i+1] <= a && i < V.size()-1) i++;
Разве эти двое не делают одно и то же? Почему я получаю WA со вторым, а не первым? Не могли бы вы указать тестовый сценарий, для которого они будут отличаться?
Например, в тестовом примере:
V = 5,7,10,12
а = 11
Оба заканчиваются i = 2,
Еще одна похожая проблема, которую я получаю, это:
У меня есть другой список отсортированных значений, скажем, V2, который я пересекаю. Для каждого значения x я пытаюсь найти наибольшее число в V, которое меньше или равно x. Это то, что я делал раньше:
while (V[i] <= x && i < V.size()) {
i++;
}
i--;
На каждой итерации V2 я не устанавливал значение i равным 0, а вместо этого продолжал с того места, где был раньше. (Потому что V2 был отсортирован)
Так что если у меня есть:
V = 5 7 10 12
V2 = 7 8 10 11 13
Мой код вернул бы индекс 1, 1, 2, 2, 3. Даже тогда я получал WA с этим. : /
Но когда перед каждой итерацией через V2 я делал i = 0, я получал AC. Сейчас это медленно, а это не то, что я хотел сделать изначально, но я понятия не имею, почему это не работает, когда я не сбрасываю i в 0.
Помогите, ребята? : 3
РЕДАКТИРОВАТЬ:
Вы можете заменить значения здесь.
vector <int> V1 = {1,2,3};
int target = 5;
int index = 0;
while (V1[index] <= target && index < V1.size()) { index++; }
index--;
cout << index << endl;
index = 0;
while (V1[index+1] <= target && index < V1.size()-1) index++;
cout << index << endl;
Это ^ всегда, кажется, возвращает один и тот же ответ для каждого предоставленного тестового примера.
Решение
Поскольку массив для поиска уже отсортирован, вы можете использовать различные функции двоичного алгоритма поиска, чтобы найти правильное значение. Использование бинарного поиска O(log n) сложность, чтобы найти значение, в отличие от поиска, который вы используете, который O(n),
Иными словами, если в вашем отсортированном массиве было миллион чисел, поиск один за другим, чтобы найти правильное значение, потребовал бы максимум миллиона сравнений. Использование бинарного поиска потребовало бы максимум 20 сравнений, где сравнение выполняется только по среднему элементу сокращающей последовательности (последовательность сокращается пополам каждый раз, когда число не найдено).
В <algorithm> есть станд :: upper_bound это может быть использовано для бинарного поиска. Хитрость заключается в том, чтобы вернуть значение перед итератором std::upper_bound возвращает, и убедитесь, что вы не выходите за пределы в нижней части значений для поиска.
#include <iostream>
#include <algorithm>
int getIndex(const std::vector<int>& V, int val)
{
auto iter = std::upper_bound(V.begin(), V.end(), val);
if ( iter != V.begin())
// return the index of the item before the found item
return std::distance(V.begin(), std::prev(iter));
// return the first item
return 0;
}
int main()
{
std::vector<int> V = {5,7,10,12};
std::vector<int> V2 = {7, 8, 10, 11, 13};
std::for_each(V2.begin(), V2.end(), [&](int val)
{std::cout << getIndex(V, val) << " ";});
}
Обратите внимание, что в примере не проверяется, меньше ли значение для поиска значений в вашем векторе. Вам необходимо добавить эту проверку и вернуть значение, обозначающее, что число выходит за пределы допустимого диапазона.
Другие решения
Других решений пока нет …
detector