title: How to find all values that occur more than n/k times in an array?
body: <p>I'm pursuing the <a href="https://www.coursera.org/learn/algorithms-part1" rel="noreferrer">Algorithms, Part I</a> course on Coursera, and one of the interview questions (ungraded) is as follows:</p>
  
  <blockquote>
    <p><strong>Decimal dominants</strong>. Given an array with n keys, design an algorithm to find all values that occur more than n/10 times. The expected
    running time of your algorithm should be linear.</p>
  </blockquote>
  
  <p>It has a hint: </p>
  
  <blockquote>
    <p>determine the (n/10)th largest key using quickselect and check if it
    occurs more than n/10 times.</p>
  </blockquote>
  
  <p>I don't understand what does the n/10 largest key have to do with n/10 repeated values. It won't tell me which values occur more than n/10 times.</p>
  
  <p>There's a <a href="https://ac.els-cdn.com/0167642382900120/1-s2.0-0167642382900120-main.pdf?_tid=e9b63ea4-6df0-4d84-b3fe-d5a22301e2a0&amp;acdnat=1527477191_c7e63434dcae83c5eef7d925082f653f" rel="noreferrer">paper</a> that finds a more general solution for n/k, but I'm having a hard time understanding the code in the paper.</p>
  
  <p>One way to solve it is to sort the input array, and then make another pass counting the occurrence of each distinct value. That'll take O(nlogn) + O(n) time, which is more than what the question asks for.</p>
  
  <p>Ideas?</p>