How many different elements in a vector?

[Nebur]

Hi everybody,

I am asked to make a program that given n, and n integer numbers, returns how many of these integers are different. I have to do it in an extremely efficient way.

To do so, i use 2 functions, one to sort the vector and another one to determine if an element is included in the vector by dichotomic search.

However, the program doesen't work, for example if n = 5, and the five numbers are 99 99 99 99 99, the amount of different numbers returned is 2, when it should be 1. I have no clue why this happens.

Some notes: I use bubble sort because (i think) is the most efficient when the vector is "almost sorted" as in the case. Also I use this function to be able to use dicotomich search wich otherwise i wouldn't be able to use.

Here is the code:

#include <iostream>
#include <vector>
using namespace std;

bool included(const vector<int>& v, int n, int left, int right) {
	if (left > right) return false;
	int pos = (left + right)/2;
	if (v[pos] > n) return included(v, n, left, pos-1);
	if (v[pos] < n) return included(v, n, pos+1, right);
	return true;
}

void bubble_sort(vector<int>& a) {
	int last = a.size() - 1;
	bool sorted = false;
	while (not sorted) {
		sorted = true;
		for (int i = 1; i < last; ++i) {
			if (a[i] < a[i-1]) {
				swap(a[i-1], a[i]);
				sorted = false;		
			}
		}
		--last;
	}
}

int main () {
	int n;
	cin >> n;
	vector<int> coefs(n);
	
	int k = 0;
	for (int i = 0; i < n; ++i) {
		bubble_sort(coefs);
		int m;
		cin >> m;
		if (not included(coefs, m, 0, k)) {
			coefs[k] = m;
			++k;
		} 
	}
	cout << k << endl;
}

Any help will be welcome and very apreciated!

Thanks!

[ne555]

vector<int> coefs(n); creates a vector of size `n', filled with 0.
You seem to use `k' to keep the size of the vector, that you use when doing the binary_search(), but when you sort() you use the whole vector

So you have a sorted vector {0, 0, 0, 0, 99} and search for 99 only in the first element.

Your sort function is incorrect

int last = a.size() - 1;
for (int i = 1; i < last; ++i)

`last' is a valid position, but you never consider it.


> I use bubble sort because (i think) is the most efficient when the vector is "almost sorted"
Nope. Consider by instance v = {1,2,3,4,5,6,7,8,9,0}. It's ``almost sorted'', you simply need to move the 0 to the first position.
However, bubble-sort would move the 0 only one position in each pass
v = {1,2,3,4,5,6,7,8,9,0}
v = {1,2,3,4,5,6,7,8,0,9}
v = {1,2,3,4,5,6,7,0,8,9}
...
So the time would be O(n^2)

Insertion-sort would work a lot better with a O(n)


However, I don't see a reason for you to maintain the whole vector sorted at each step.
You could simply do

read v
sort v | uniq | count

Or, as you are implementing a set, simply use std::set

[Nebur]

You mean, first reading the vector, then sorting it with insertion and then counting how many different elements it has?

[ne555]

Yes, but no need to use insertion-sort, as there are a lot of better O(n lg n) algorithms.

[Nebur]

Ok, i will use merge sort. But how can you count how many diferent elems eficiently?

Thanks