CODEWITHSUNDEEP
c++vectorcomparison
Kirtiman Sinha
Kirtiman Sinha

Reputation: 1011

C++: Efficient way to check if elements in a vector are greater than elements in another having same indices?

I have a vector < vector <int> > like so:

v = {{1,2,3}, {4,2,1}, {3,1,1}....}}

All v's elements like v[0], v[1], v[2]... have the same size. There may be duplicate elements.

What I am trying to do is to find and delete vectors (like v[2]) that are "majorized" by another vector (like v[1]), i.e. all elements of v[1] are greater than/equal to the respective elements(in order of indices) in v[2].

A naive way of doing this would be to loop thorough v and compare each vector with another vector and further compare each element with another vector's element.

But I feel there must a better way to do this without getting O(n^3) in the number of elements of all the vectors in v.

If multiple vectors are equal, I need only one of them (i.e delete all except one). A random choice would be sufficient.

Any thoughts or ideas are appreciated!

Upvotes: 3

Views: 1345

Answers (1)

Vaughn Cato
Vaughn Cato

Reputation: 64308

This is called the maxima of a point set. For two and three dimensions, this can be solved in O(n log n) time. For more than three dimensions, this can be solved in O(n(log n)^(d − 3)  log log n) time. For random points, a linear expected time algorithm is available.

Upvotes: 1

Related Questions