Task
Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees. People can be very tall!
Example
For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].
Input/Output
-
[execution time limit]
4 seconds (py3) -
[input] array.integer a
Ifa[i] = -1, then the ith position is occupied by a tree. Otherwisea[i]is the height of a person standing in the ith position.
Guaranteed constraints:1 ≤ a.length ≤ 1000,-1 ≤ a[i] ≤ 1000. -
[output] array.integer
Sorted arrayawith all the trees untouched.
My Solution
def mergeSort(array, left, right):
if right - left < 2:
return
mergeSort(array, left, left + (right - left) // 2)
mergeSort(array, left + (right - left) // 2, right)
temp = [0 for i in array]
lCur = left
rCur = left + (right - left) // 2
tCur = left
while lCur < left + (right - left) // 2 and rCur < right:
if array[lCur] < array[rCur]:
temp[tCur] = array[lCur]
lCur += 1
tCur += 1
else:
temp[tCur] = array[rCur]
rCur += 1
tCur += 1
while tCur < right:
if lCur == left + (right - left) // 2:
temp[tCur] = array[rCur]
rCur += 1
tCur += 1
else:
temp[tCur] = array[lCur]
lCur += 1
tCur += 1
array[left:right] = temp[left:right]
return
def sortByHeight(a):
people = [height for height in a if height > -1]
mergeSort(people, 0, len(people))
i = 0
j = 0
while i < len(a):
if a[i] == -1:
i += 1
else:
a[i] = people[j]
i += 1
j += 1
return a