You can get your counts in O(N) time by using a hashmap (std::unordered_map
). Something like:
std::vector<int> x = buildMyVector();
std::unordered_map<int, int> counts;
for(int val : x)
counts[val]++;
Then a second O(N) operation could do the update:
for(int& val : x)
{
int count = counts[val];
if(count > 1) // could technically skip this since (1 - 1) / 2 is 0
val += (count - 1) / 2;
}
However, since x is a vector<int>
, integer division will always be used; i.e. you will not get 2.5 in your example, you'll just get two. If you want 2.5, you'll need to change vector<int>
to vector<double>
(or float
). This could mess up your comparisons, though (should 2.0000000001 == 2.0?), so you'd need to rethink how you'd handle that. If the input is always int
but the output can be double
, maybe this:
std::vector<double> output;
output.reserve(x.size());
for(int val : x)
{
double newVal = static_cast<double>(val);
int count = counts[val];
if(count > 1) // could technically skip this since (1 - 1) / 2 is 0
newVal += (count - 1.0) / 2.0;
output.push_back(newVal);
}