lower_bound and upper_bound от HackerRank задача

Jovanna 186 Точки

lower_bound and upper_bound от HackerRank задача

Здравейте,

задачата е за работа с lower_bound and upper_bound; Направих няколко оптимизации на решението, но все още дава на няколко теста "Terminated due to timeout". Някакви идеи?

(оптимизации: максималния елемент го намирам още на вход; После проверка, ако числото е > от максималния, директно принтя изход )

Условието е :
You are given integers in the sorted order. Then you are given queries. In each query you will be given an integer and you have to tell whether that integer is present in the array, if so you have to tell at which index it is present and if it is not present you have to tell the index at which the smallest integer that is just greater than the given number is present.

The first line of the input contains the number of integers . The next line contains integers in sorted order. The next line contains , the number of queries. Then lines follow each containing a single integer .
If the same number is present multiple times, you have to print the first index at which it occurs.

Ето кода:

https://pastebin.com/0rcUFKEp

Тагове:

15/05/2018 21:54:48 C++ Programming

MartinPaunov 77 Точки

Здравей,

Определено си се захванала с интересна задачка. Като цяло в повечето задачи където ни казват, че търсим нещо в сортирана структора се очаква да използваме бинарно търсене (не че винаги ще е така), като само това промених в кода ти и задачата мина успешно на всички тестове в HackerRank.

В товоя код използваш функцията find:

if (find(v.begin(), v.end(), number_to_search) != v.end())

за да провериш дали елемента се намира някъде във вектора, замени този ред със следния:

if (std::binary_search(v.begin(), v.end(), number_to_search))

и кода ти минава, като минават и всички тестове.

Можеш да направиш и няколко други оптимизации в кода ти, например в условието ти изрично е казано, че елементите са в сортиран ред. Не е необходимо да правиш проверка за да намериш най-големия елемент в началото, това е по една операция за всеки елемент. Малко промених кода ти ето пейстбин и това решение мина на всички тестове.

Поздрави

15/05/2018 23:49:13 16/05/2018 00:29:59

kolioi 641 Точки

Правиш много излишни неща. Достатъчно е да вкараш числата във вектор и след това за всяко query да викаш lower_bound().

Нещо такова

int main() 
{
    int n, values, q;
    vector<int> v;
    
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> values;
        v.push_back(values);
    }
    
    cin >> q;
    for(int i=0; i<q; i++)
    {
        cin >> values;
        auto it = lower_bound(v.begin(),v.end(),values);

        if(values == *it)
            cout << "Yes ";
        else
            cout << "No ";

        cout << it-v.begin()+1 << endl;
    }
    
    return 0;
}

it е vector<int>::iterator

16/05/2018 00:25:17 16/05/2018 00:27:30

Jovanna 186 Точки

Много благодаря!! Красив код сте написали!

kolioi: Мисля, че lower_bound ще върне позицията на нулевия елемент, в слчай че (и двете заедно):

values го няма във вектора от входа и ако values е по-малко от най-малката стойност от вектора:

auto it = lower_bound(v.begin(),v.end(),values);

а търсим изход позицията на последния елемент в случая + 1 , т.е, броя на елементите, това очаква изхода. Или бъркам?

Поздрави и от мен

16/05/2018 19:12:13 16/05/2018 19:13:12

kolioi 641 Точки

По условие, ако числото го няма в масива, трябва да отпечатаме индекса на най-малкото число от масива, което е по-голямо от числото което търсим (иначе казано - първото срещнато число от масива, което е по-голямо от търсеното). Тъй като подаваме на lower_bound() параметри v.begin() и v.end(), то ще ни върне итератор в тези граници. Ако търсеното число е по-малко от първия (най-малкия) елемент на масива, очевидно числото го няма в масива и lower_bound() ще върне v.begin(), което е коректно. Ето ти една малка програмка за тестване

vector<int> v{ 2,4,6,8 }, q{ 6,3,-1 };

for each (int n in q)
{
	vector<int>::iterator it = lower_bound(v.begin(), v.end(), n);

	if (n == *it)
		cout << "Yes ";
	else
		cout << "No ";

	cout << it - v.begin() + 1 << endl;
}

Между другото, всеки може да види кода на lower_bound() в хедър файла algorithm и как точно работи.

16/05/2018 22:52:01 18/05/2018 10:25:50

Jovanna 186 Точки

Martin, kolioi, много благодаря за съветите и помощта, радвам се че сте във форума и помагате !!!!

18/05/2018 13:21:30