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

Автор levonstepan, 10 лет назад, По-русски

You are given an array S[1 . . . n] of real numbers, some positive and some negative.

Design an O(n log n)-time algorithm that determines whether S contains two elements S[i] and S[j] such that S[i] = −S[j]. The algorithm returns a “yes” if there is such a pair, and “no” otherwise. If the array S contains the element 0, then the algorithm always returns a “yes”.

Your algorithm has to be in-place (i.e. you can use only constant additional memory).

I solved it using Heap Sort, but is there any other solution? Because it is assumed that the student doesn't know Heap Sort yet.

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

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

sort and two pointers Lyova.

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

    Yeah I did the same two-pointer thing! But what about the sorting part? which sort do you mean Sparlik? For example quick sort is O(n^2) in worst case. Merge Sort uses additional memory. (not in-place)

    It is not assumed that the student must know Heap sort at this point of time.

    That's why I am looking for an algorithmic solution (like a divide-and-conquer algorithm).

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

      there is an in-place version of mergesort bitch.

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

        Look on the Wiki page you mouse-faced faggot! https://en.wikipedia.org/wiki/Sorting_algorithm

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

          Quicksort can be written in in the worst case since one can find a median in linear time.

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

            Could you please provide a link to an article where Quicksort is implemented in nlogn in the worst case. Because selecting random pivot takes O(1) and that's why algorithm runs in nlogn, if you waste N time to find the median, I believe the algorithm will run in O(n^2).

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

              Google something like linear time median.

              Quicksort runs in because in each step we do something in O(r - l) time and then call sort(l, mid) and sort(mid + 1, r) there mid ~ (l + r) / 2.

              So we can find median in O(r - l) time using algorithm which splits array into n/5 groups, for example.

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

          I made you my bitch!

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

          it's for data structures with only swap operation allowed. However, we can use linked list in this problem. For linked lists, stable in-place merge algorithm is trivial.

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

            You cannot use additional memory like a linked list. (as I mentioned we are asked for an in-place algorithm)