rezzaque's blog

How do I find k closest integers in an array to its median?
By rezzaque, history, 8 years ago, In English

The array A is not sorted and has n distinct integer elements. Our aim to find k<=n elements that are closest to the median of this array. The distance is in terms of absolute value of the element and median's difference. The algorithm asked must have O(n) complexity.

  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's say the range of elements is 1 to X. Then take an array of size X and store the counts of elements of this array. As all elements have count 1, the middle marked element is the median. Now loop k/2 to the left and right side of this median index. Complexity: O(n) for storing counts, then O(n) for looping k/2 on both sides, hence overall complexity is O(n).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +87 Vote: I do not like it

First find the median using nth_element. Then replace each value V by |V-median|. Call again nth_element for the k-th largest new value, let's denote it by X. Now you can identify the wanted elements — those for which the new value is <= X.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How does the nth_element work in O(n)?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      It's amortised complexity. It works just like quick sort, but you only call the function recursively on the half that contains your element, instead of both halves.

      → Reply