Replace reapeted element in an array

Question

I have been trying to replace element occurring multiple times in an array with a particular formula. To be exact consider that in an array value x has occurred k times I need to replace all the occurrences of x with x+(k-1)/2. for example say 2 has occurred 2 times then replace all occurrence of 2 with 2.5.

My Idea of doing this is to maintain an array of same length as the input as a flag to check whether a particular element is checked.and this takes O(n^2) time. The code is as follows.

NumericVector replaceRepetedValues(NumericVector x){
   logicalVector flag(x.size());
   for(int i=0;i<x.size();i++){
     int count=0;
     std::vector<int> index;

     for(int j=i+1;j<x.size();j++){
      if(x[i]==x[j]){
       count++;
       index.push_back(j);           
      }
     }
     if(count>0){
       for(std::vector<int>::iterator it=index.begin();it!=it.end();it++){
         x[*it]=x[*it]+(count-1)/2;
       }
     } 
   }
}

Is there any efficient implementation for this problem?

Answer 1

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);
}