快排题解 | #字符串出现次数的TopK问题#

快速排序解题
topK 问题应该用堆排序

import random

def less(pair1, pair2):
    # 按count从大到小排列
    # 按从小到大
    if pair1[1] != pair2[1]:
        return pair1[1] < pair2[1]
    else:
        return pair1[0] > pair2[0]

class Solution:
    def quick_sort(self, count, start, end):
        if start < end:
            l = start
            r = end
            index = random.randint(l, r)
            # count[index], count[l] = count[l], count[index]
            pivot = count[l]
            while l < r:
                while l < r and less(count[r], pivot):
                    r -= 1
                if l < r:
                    count[l] = count[r]
                    l += 1
                while l < r and not less(count[l], pivot):
                    l += 1
                if l < r:
                    count[r] = count[l]
                    r -= 1
            count[l] = pivot
            self.quick_sort(count, start, l - 1)
            self.quick_sort(count, l + 1, end)

    def topKstrings(self , strings , k):
        # write code here
        count = {}
        for i in range(len(strings)):
            count[strings[i]] = count.get(strings[i], 0) + 1
        count = list([k, v] for k, v in count.items())
        self.quick_sort(count, 0, len(count) - 1)
        return count[:k]