Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- 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.
- """
- from random import randint
- 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, fnuts, fbolts, compare):
- # write your code here
- self.nuts=fnuts
- self.bolts=fbolts
- if not self.nuts or not self.bolts or len(self.nuts)!=len(self.bolts):
- return
- self.quicksort(0,len(self.nuts)-1,compare.cmp)
- def quicksort(self,l,r,cmp):
- if l>=r:
- return
- pivot=self.bolts[randint(l,r)]
- i,j=l,r
- while i<=j:
- while i<=j and cmp(self.nuts[i],pivot)==-1:
- i+=1
- while i<=j and cmp(self.nuts[j],pivot)==1:
- j-=1
- if i<=j:
- self.nuts[i],self.nuts[j]=self.nuts[j],self.nuts[i]
- i+=1
- j-=1
- if i==j:
- self.quicksort_bolt(l,r,i,cmp)
- else:
- self.quicksort_bolt(l,r,i-1,cmp)
- self.quicksort(l,j,cmp)
- self.quicksort(i,r,cmp)
- return
- def quicksort_bolt(self,l,r,index,cmp):
- if l>=r:
- return
- pivot=self.nuts[index]
- i,j=l,r
- while i<=j:
- while i<=j and cmp(pivot,self.bolts[i])==1:
- i+=1
- while i<=j and cmp(pivot,self.bolts[j])==-1:
- j-=1
- if i<=j:
- self.bolts[i],self.bolts[j]=self.bolts[j],self.bolts[i]
- i+=1
- j-=1
- return
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement