Блог пользователя Cerberus14

Автор Cerberus14, история, 3 месяца назад, По-английски,

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.

 
 
 
 
  • Проголосовать: нравится  
  • +18
  • Проголосовать: не нравится  

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually I did the same solution with a little bit difference. As we do not know if all the k closest ones sit on the right part of the array I created a function that looks for the closest element in each way and when it finds it changes its value to infinity(I stored sorted order in the initial array from the big hash array). However, our solution is a bit naive because the array might have a biggest value X that is equal to 10^9 then it does not really matter that our solution is linear timed. See, the thing is our instructor was expecting a solution using a logic similar to quicksort's partitions. I could not come up with a way for that.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +87 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks, great solution.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How does the nth_element work in O(n)?

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.