new_algos's blog

By new_algos, history, 5 weeks ago, In English,

You are given an array of n integers. Your task is to calculate the median of each window of k elements, from left to right.

The median is the middle element when the elements are sorted. If the number of elements is even, there are two possible medians and we assume that the median is the smaller of them.

1≤k≤n≤2⋅105

1≤xi≤109

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

[Edit: oops, I misread.]

»
5 weeks ago, # |
Rev. 8   Vote: I like it +4 Vote: I do not like it

Honestly, I can't come up with an elegant solution, so I'll tell a couple of slightly data-structure-heavy ones instead.

idea number one
idea number two, probably wrong
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    More or less the same as your first idea but you can use ordered_set there so you don't have to implement almost anything.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks , Solved using implicit treap.

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Am i missing something or can we just use two heaps?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think there is need for clarification.

    I see two heaps as:
    1) build two sets (size of k / 2 and k — k / 2) for a[1..k]. Elements of first set will be not greater than elements of second.
    2) for shifting window by 1 to the right, we need to hold sets of that size.
    3) Then for each step answer is biggest element of first set.

    Cool idea for O(nlogn). But maybe there is need for O(n)?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Heaps have a pretty small constant so it should pass. Everything i can think of involves keeping a sort in some way, so I can't really think of an O(n) approach.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How using just heaps (not sets) remove concrete element?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          maybe use two heaps, heap 1 save the original elements, heap 2 save the deleted elements.

          When you insert an element push it into heap 1.

          When you remove an element push it into heap 2.

          When you pop the biggest/smallest from the heap, if the element on the top of heap 1 is the same as the top of heap 2, then remove this element from both heaps. Keep on removing until heap 1 is empty/found an element which is in heap 1 but not in heap 2.

          For same elements you can tie it with an id, and the id must be different.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it