Zliczanie elementów w wektorze lub w tablicy za pomocą wyszukania binarnego.

pytanie zadane 3 października 2019 w C i C++ przez Milo Obywatel (1,180 p.)

Mam takie zadanie do wykonania: https://main2.edu.pl/c/kurs-podstaw-algorytmiki-druga-e/p/akc/ .

Wiem jak za pomocą wyszukania binarnego sprawdzić czy dany element występuje w wektorze lub w tablicy, ale nie wiem jak je zliczyć.

Nie chciałbym też otrzymać rozwiązania tego zadania, lecz podpowiedź jak to rozwiązać.

komentarz 3 października 2019 przez tkz Nałogowiec (42,000 p.)

https://en.cppreference.com/w/cpp/algorithm/count

komentarz 3 października 2019 przez Milo Obywatel (1,180 p.)

Nie wiem czy się załapię z tym w limicie czasu.

komentarz 3 października 2019 przez tkz Nałogowiec (42,000 p.)

Sprawdź bo inaczej się nie przekonasz.

komentarz 3 października 2019 przez Milo Obywatel (1,180 p.)

@tkz, sprawdzarka wyrzuca o przekroczeniu limitu czasu.

komentarz 3 października 2019 przez Milo Obywatel (1,180 p.)

Chodzi mi o zliczenie elementów, ale z wyszukaniem binarnym bo na większych wektorach nie zajmie to więcej czasu.

komentarz 3 października 2019 przez tkz Nałogowiec (42,000 p.)

Mapa(to co poleciła osoba niżej) nie ma jakiejś doskonałej złożoności czasowej. Ale możesz spróbować.

1 odpowiedź

odpowiedź 3 października 2019 przez Szahid Pasjonat (20,930 p.)

Użyj kontenera map gdzie kluczem będzie prędkość a wartością będzie liczba jej wystąpień

komentarz 3 października 2019 przez adrian17 Ekspert (344,860 p.)

(lub unordered_map, które tutaj potencjalnie mogłoby być jeszcze szybsze.)

komentarz 3 października 2019 przez tkz Nałogowiec (42,000 p.)

Przy wstawianiu tak, ale czy przy wyszukiwaniu(bo to jest głównym problemem)? Bo o ile się nie mylę. to wyszukiwanie w uporządkowanej mapie to o(1).

komentarz 3 października 2019 przez adrian17 Ekspert (344,860 p.)

Na odwrót.

https://en.cppreference.com/w/cpp/container/map/operator_at

Complexity: Logarithmic in the size of the container

https://en.cppreference.com/w/cpp/container/unordered_map/operator_at

Complexity: Average case: constant, worst case: linear in size.

komentarz 3 października 2019 przez Milo Obywatel (1,180 p.)

Nie mam dużo wprawy w rozwiązywaniu zadań, co to mapa to wiem, ale średnio wiem jak to zrobić.

komentarz 3 października 2019 przez tkz Nałogowiec (42,000 p.)

Ajjj, dzięki za sprostowanie.

komentarz 3 października 2019 przez Szahid Pasjonat (20,930 p.)

To powiedz czego nie wiesz

komentarz 3 października 2019 przez Milo Obywatel (1,180 p.)

No właśnie nie wiem jak to zliczyć za pomocą mapy.

komentarz 3 października 2019 przez Milo Obywatel (1,180 p.)

Już to zaczaiłem.

komentarz 3 października 2019 przez Milo Obywatel (1,180 p.)

#include <iostream>
#include <vector>
#include <map>

int main()
{
	std::vector<int> N, Q;
	unsigned int n, q;
	int x;
	std::map<int, int> wyniki;

	std::cin >> n;
	for (int i = 0; i < n; i++)
	{
		std::cin >> x;
		N.push_back(x);

		wyniki[x] += 1;
	}

	std::cin >> q;
	for (int i = 0; i < q; i++)
	{
		std::cin >> x;
		Q.push_back(x);
	}

	for (int i = 0; i < q; i++)
	{
		std::cout << wyniki[Q[i]] << std::endl;
	}

	return 0;
}

Tylko przy ostatnim teście nie zalicza i łącznie daje 0pkt (trzeba mieć wszystko dobrze, aby zaliczyć).

Tak jak jest w treści, to chyba trzeba zrobić to wyszukaniem binarnym, aby zaliczyło.