Idea: quick sort
There are 3 things we have to know:
- nuts and bolts can not be compared inside. Only nuts[a] and bolts[b] are allowed to be compared.
- It's not a simple comparison with >, < or =. We are required to use 'cmp', a function from Class Comparator.
- A fixed order is in the () of cmp, 'Compare.cmp(a, b) to compare nuts "a" and bolts "b"', which means cmp(bolts[a], nuts[b]) is invalid.
"""
class Comparator:
def cmp(self, a, b)
You can use Compare.cmp(a, b) to compare nuts "a" and bolts "b",
if "a" is bigger than "b", it will return 1, else if they are equal,
it will return 0, else if "a" is smaller than "b", it will return -1.
When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
"""
class Solution:
# @param nuts: a list of integers
# @param bolts: a list of integers
# @param compare: a instance of Comparator
# @return: nothing
def sortNutsAndBolts(self, nuts, bolts, compare):
# write your code here
def quick_sort(low, high, nuts, bolts):
if low < high:
pivot = find_pivot(low, high, nuts, bolts)
quick_sort(low, pivot-1, nuts, bolts)
quick_sort(pivot+1, high, nuts, bolts)
def find_pivot(low, high, nuts, bolts):
pivot = high
left_wall = low
i = low
while i < high:
if compare.cmp(nuts[pivot],bolts[i]) == 1:
bolts[i], bolts[left_wall] = bolts[left_wall], bolts[i]
left_wall += 1
if compare.cmp(nuts[pivot], bolts[i]) == 0:
bolts[high], bolts[i] = bolts[i], bolts[high]
i -=1
i +=1
bolts[left_wall], bolts[high] = bolts[high], bolts[left_wall]
pivot = left_wall
left_wall = low
i = low
while i < high:
if compare.cmp(nuts[i], bolts[pivot]) == -1:
nuts[i], nuts[left_wall] = nuts[left_wall], nuts[i]
left_wall += 1
i += 1
nuts[left_wall], nuts[high] = nuts[high], nuts[left_wall]
# 'return pivot' has the same effect.
return left_wall
quick_sort(0, len(nuts)-1, nuts, bolts)
