Why the O(n) method is straightforward, could anybody tell me? Thank you!


  • 0
    E

    Why the O(n) method is straightforward, could anybody tell me? Thank you!


  • 1
    H

    I havent coded it but this is what I think:
    In order traversal the tree, put tree node in a list. Then swap the one bigger than its successor and the one smaller than its predecessor


  • 0
    E

    Thanks, but I have a problem. For example 1 2 3 4 5 -> 1 4 3 2 5. The 2 and the 4 are swapped. However, 4, 5 are bigger than their predecessor, and 1, 2 are smaller than their successor. How do I know which two should be swapped.


  • 0
    H

    In a sorted array of distinct elements:
    A B C D E F G
    If we swap B and F then we have:
    A F C D E B G
    We can see that the array is in ascending order until F and C, we record this and continue from C.
    then at E and B we see the order if wrong again.
    So we need to swap F (it is bigger so it comes from a later position) and B (it is smaller so it comes from a earlier position).

    There is a special case when we swap two neighbouring elements:
    ACBDEFG

    where we will only detect the broken order once.


  • 0
    E

    Thank you so much! Now, I understand it!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.