title: Efficiently normalize an array in C++
body: <p>I am looking for a way to normalize an array efficiently in C++, Normalization means converting all of your array values into values lower than or equal to n. So this:</p>
  
  <p><code>5235 223 1000 40 40</code></p>
  
  <p>Becomes:</p>
  
  <p><code>4 2 3 1 1</code> or <code>3 1 2 0 0</code></p>
  
  <p>Here are my codes</p>
  
  <pre><code>vector&lt;int&gt; normalize_array(vector&lt;int&gt; arr){
      vector&lt;int&gt; tmp(arr), ret(arr.size());
  
      sort(tmp.begin(), tmp.end());
  
      for (int i = 0; i &lt; arr.size(); ++i){
          vector&lt;int&gt;::iterator iter = find(tmp.begin(), tmp.end(), arr[i]);
          ret[i] = std::distance(tmp.begin(), iter);
      }
  
      return ret;
  }
  </code></pre>
  
  <p>The output is <code>4 2 3 0 0</code>, the above codes can not handle duplicate elements very well.
  Is there any better way to do that?</p>