LeetCode-Solutions/Python/pancake-sorting.py at master · pythonpeixun/LeetCode-Solutions · GitHub

21 lines (19 loc) · 547 Bytes

# Time: O(n^2)

# Space: O(1)

class Solution(object):

def pancakeSort(self, A):

"""

:type A: List[int]

:rtype: List[int]

"""

def reverse(l, begin, end):

for i in xrange((end-begin) // 2):

l[begin+i], l[end-1-i] = l[end-1-i], l[begin+i]

result = []

for n in reversed(xrange(1, len(A)+1)):

i = A.index(n)

reverse(A, 0, i+1)

result.append(i+1)

reverse(A, 0, n)

result.append(n)

return result

Expand file tree