Алгоритм — C ++, как найти ключ карты, которая имеет ближайшее значение данного значения
Я хочу найти ключ ближайшего значения к отсортированной карте. Например:
#include <iostream>
#include <map>
int main ()
{
std::map<int,int> mymap;
mymap[1]=10;
mymap[2]=40;
mymap[3]=100;
mymap[4]=200;
mymap[5]=500;
int wantedvalue=50;
int wantedindex=mymap.whatshouldIdohere(wantedvalue);
std::cout<<"The closest value of "<<wantedvalue<<" in the map is located";
std::cout<<" on "<<wantedindex<<" and is "<<mymap[wantedindex]<<std::endl;
//Should be:
//The closest value of 50 in the map is located on 2 and is 40
return 0;
}
Код, упомянутый в комментариях, должен возвращать индекс, поскольку искомое значение 50 ближе ко второй позиции, чем любая другая.
Есть ли способ, которым я могу это сделать?
PS: я знаю, что у меня может быть «для», поиск по всей карте и остановка, когда я найду значение, превышающее заданное значение, но худшее время выполнения для этого — поиск по всей таблице. Кроме того, мне нужно запустить это много раз, поэтому я ищу что-то лучшее, чем это.
Решение
Используя этот контейнер, вы можете использовать только линейный поиск. Например, вы можете использовать стандартный алгоритм std::min_element, В противном случае вы должны использовать другой контейнер.
Вот ты где
#include <iostream>
#include <map>
int main()
{
std::map<int, int> mymap;
mymap[1] = 10;
mymap[2] = 40;
mymap[3] = 100;
mymap[4] = 200;
mymap[5] = 500;
int wantedvalue = 50;auto it = std::min_element( mymap.begin(), mymap.end(),
[&](const auto &p1, const auto &p2)
{
return
std::abs(( long )p1.second - wantedvalue) <
std::abs(( long )p2.second - wantedvalue);
});
std::cout << "The closest value of " << wantedvalue << " in the map is located";
std::cout << " on " << it->first << " and is " << it->second << std::endl;
return 0;
}
Выход программы
The closest value of 50 in the map is located on 2 and is 40
Другие решения
Других решений пока нет …