Алгоритм — 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: я знаю, что у меня может быть «для», поиск по всей карте и остановка, когда я найду значение, превышающее заданное значение, но худшее время выполнения для этого — поиск по всей таблице. Кроме того, мне нужно запустить это много раз, поэтому я ищу что-то лучшее, чем это.

1

Решение

Используя этот контейнер, вы можете использовать только линейный поиск. Например, вы можете использовать стандартный алгоритм 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
2

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector