LintCode 399 [Nuts & Bolts P

原题

给定一组 n 个不同大小的 nuts 和 n 个不同大小的 bolts。nuts 和 bolts 一一匹配。 不允许将 nut 之间互相比较，也不允许将 bolt 之间互相比较。也就是说，只许将 nut 与 bolt 进行比较， 或将 bolt 与 nut 进行比较。请比较 nut 与 bolt 的大小。

样例
Nuts 用一个string数组表示 nuts [] = ['ab','bc','dd','gg']. Bolts 也用一个string数组表示 bolts[] = ['AB','GG', 'DD', 'BC']. 我们将提供一个比较函数，以比较 nut 与 bolt 的大小。将 nuts 进行升序排序，使得 nuts 与 bolts 位置对等。
比如 nuts = ['ab','bc','dd','gg'], bolts = ['BC','AA','DD','GG']

解题思路

• Selection Sort - 利用partition的思想
  因为Nuts之间，Bolts之间都是不能相互比较的，所以思路就是随机选择一个Nut来partition Bolts然后再反过来用那个已经在正确位置的Bolt来partition Nuts
• 初始：cc aa dd bb
• 随机找到BB，partition之后
• aa bb cc dd （cc, dd的顺序不确定）
• 之后再拿bb去反过来partition，得到
• AA BB DD CC
• 递归向下，分别左右sort
• 注意比较的时候compare函数只能
• partition函数的执行过程，模拟

pivot是4，通过for循环找到，交换到第一位，并记住pivot_partner = 4
开始：[4, 3, 2, 9, 5]
5 > 4: [5, 3, 2, 9, 5]
3 < 4: [5, 3, 2, 9, 3]
9 > 4: [5, 9, 2, 9 , 3]
2 < 4: [5, 9, 2, 2, 3]
此时L在二号位，让nums[L] = pivot_partner
[5, 9, 4, 2, 3] =>保证了4前面都是大于4的，后面都是小于4的

完整代码

# 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
        if nuts == [] or bolts == [] or compare is None:
            return 
        self.compare = compare
        self.quickSort(nuts, bolts, 0, len(nuts) - 1)
        
    def quickSort(self, nuts, bolts, left, right):
        if left >= right:
            return 
        split_nut_pos = self.partition(nuts, bolts[left], left, right)
        split_bolt_pos = self.partition(bolts, nuts[split_nut_pos], left, right)
        self.quickSort(nuts, bolts, left, split_nut_pos - 1)
        self.quickSort(nuts, bolts, split_nut_pos + 1, right)
        
    def partition(self, items, pivot, left, right):
        if items == [] or pivot == None:
            return
        
        # 首先把pivot换到数组的第一个位置
        for i in range(left, right + 1):
            if self.compare.cmp(pivot, items[i]) == 0 \
                or self.compare.cmp(items[i], pivot) == 0:
                items[left], items[i] = items[i], items[left]
                break
        
        # 如果pivot是AA,此时pivot_partner就是aa
        pivot_partner = items[left]
        while left < right:
            while left < right and \
                (self.compare.cmp(pivot, items[right]) == -1 \
                or self.compare.cmp(items[right], pivot) == 1):
                right -= 1
            items[left] = items[right]
            
            while left < right and \
                (self.compare.cmp(pivot, items[left]) == 1 \
                or self.compare.cmp(items[left], pivot) == -1):
                left += 1
            items[right] = items[left]
            
        items[left] = pivot_partner
        return left