Przejdź do zawartości

Kody źródłowe/Znajdowanie duplikatów w posortowanej liście

Z Wikibooks, biblioteki wolnych podręczników.
Metoda • Znajdowanie duplikatów w posortowanej liście
Metoda
Znajdowanie duplikatów w posortowanej liście
Na podstawie posortowanej listy w czasie liniowym znajduje duplikaty. Ten algorytm pokazuje wielokrotne wystąpienia duplikatów.

C++

[edytuj]
#include <random>
#include <stdint.h>
#include <algorithm>

using namespace std;

const int Count = 500;
const int Space = 20000;
vector<int16_t> vec, duplicateVec;

void generate()
{
	mt19937 gen(0);
	uniform_int_distribution<int16_t> dis(0, Space - 1);
	for (int i = 0; i<Count; i++)
		vec.push_back(dis(gen));
}

vector<int16_t> findDuplicates(vector<int16_t> vec)
{
	vector<int16_t> duplicates;
	int16_t prev = 0;
	bool firstInGroup = true;
	for (int i = 0; i < vec.size(); i++)
	{
		if (i == 0 || vec[i] != prev)
		{
			prev = vec[i];
			firstInGroup = true;
		}
		else
		{
			if (firstInGroup)
				duplicates.push_back(vec[i - 1]);
			firstInGroup = false;
			duplicates.push_back(vec[i]);
		}
	}
	return duplicates;
}

void printDuplicates(vector<int16_t> duplicateVec)
{
	for (int16_t n : duplicateVec)
		printf("%d\n", n);
}

int main()
{
	generate();
	sort(vec.begin(), vec.end());
	duplicateVec = findDuplicates(vec);
	printDuplicates(duplicateVec);
	return 0;
}