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

Question

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ć.

Comments

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

---

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

---

Sprawdź bo inaczej się nie przekonasz.

---

@tkz, sprawdzarka wyrzuca o przekroczeniu limitu czasu.

---

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

---

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

Answer 1

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

Comments

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

---

Już to zaczaiłem.

---

#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.

---

Po co Ci ten vector. Pakuj od razu do mapy. Będzie szybciej

---

Nadal ostatniego tylko nie zalicza.