本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站，刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是排序相关题目题解总结。

[TOC]

排序

快速排序

用于求解 Kth 问题，使用快速排序的partition()进行实现，需要首先打乱数组，否则最坏情况下时间复杂度为O(N^2)。

堆排序

用于求解 TopK 问题，通过维护一个大小为K的堆，堆中的元素就是TopK elements；

堆排序也可以用于求解 Kth 问题，堆顶元素就是 Kth elements；
快速选择也可以求解 TopK Elements 问题，因为找到 Kth Element 之后，再遍历一次数组，所有小于等于 Kth Element 的元素都是 TopK Elements；

因此快速选择和堆排序都可以求解 Kth Element 和 TopK Elements 问题。

桶排序

使用空间换时间，首先统计出数组中元素的频次。接着，将数组中的元素按照出现频次进行分组，即出现频次为 i 的元素存放在第 i 个桶。最后，从桶中逆序取出前 k 个元素；
桶排序使用Hashmap散列表。

56. 合并区间

题目描述

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路

将区间按起始元素排序，新建返回res数组，遍历所有区间；

若res为空或res中最后一个区间的结束元素小于当前区间的起始元素，则无需合并，直接将该区间添加到res中；
若res中最后一个区间的结束元素大于当前区间的起始元素，则需要合并，将res最后区间的结束元素置为原来的值与当前区间结束值的最大值。

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        intervals = sorted(intervals, key=lambda x:x.start)
        res = []
        for t in intervals:
            if not res or res[-1].end < t.start:
                res.append(t)
            else:
                res[-1].end = max(res[-1].end,t.end)
        return res

57. 插入区间

题目描述

给出一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:

1 2	输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]]

示例 2:

1
2
3

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

解题思路

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        
        cur = 0
        res = []
        while cur < len(intervals) and intervals[cur][1] <  newInterval[0]:
            res.append(intervals[cur])
            cur += 1
        while cur < len(intervals) and intervals[cur][0] <=  newInterval[1]:
            newInterval[0] = min(intervals[cur][0], newInterval[0])
            newInterval[1] = max(intervals[cur][1], newInterval[1])
            cur += 1
        res.append(newInterval)
        while cur < len(intervals):
            res.append(intervals[cur])
            cur += 1
        return res

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        
        intervals.append(newInterval)
        intervals = sorted(intervals, key = lambda x:x[0])
        
        res = [intervals[0]]
        for i in range(1, len(intervals)):
            if intervals[i][0] <= res[-1][1]:
                res[-1][1] = max(intervals[i][1], res[-1][1])
            else:
                res.append(intervals[i])
        return res

75. 颜色分类

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:

不能使用代码库中的排序函数来解决这道题。
示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路

设置两个头尾指针，头指针p0指向的位置是0该放置的位置，尾指针p2指向的位置是2该放置的位置。
i用来遍历整个数组，碰到0把它和p0指向的数交换，碰到2把它和p2指向的数交换，碰到1继续向后遍历。
有点类似快速排序的分割数组这一步。

class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        p0, p2 = 0, len(nums) -1 
        i = 0
        while i <= p2:
            if nums[i] == 0:
                nums[i],nums[p0] = nums[p0], nums[i]
                i += 1
                p0 += 1
            elif nums[i] == 2:
                nums[i], nums[p2] = nums[p2], nums[i]
                p2 -= 1
            else:
                i += 1

147. 对链表进行插入排序

题目描述

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：

输入: 4->2->1->3
输出: 1->2->3->4
示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路

插入排序：插入排序的实现上，通常采用 in-place 排序（即只需用到O(1)的额外空间的排序），用指针 head 逐一向后遍历

申请一个 dummyHead 节点，其下一个节点指向头结点。如果要在头结点出插入，dummyHead 会给我们带来便利；
当 head 的值不大于下一节点值，就进行遍历下一节点；
当 head 的值大于下一节点，那么就将 head 的下一节点取出，从前向后扫描，在第一个比它的值大的节点之前插入该节点。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        while head.next:
            if head.val <= head.next.val:
                head = head.next
            else:
                temp = head.next
                q = dummy
                head.next = head.next.next
                while q.next and q.next.val < temp.val:
                    q = q.next
                temp.next = q.next
                q.next = temp
        return dummy.next

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        
        
        while head and head.next:
            if head.val <= head.next.val:
                head = head.next
            else:
                pre = dummy
                while pre.next and pre.next.val <= head.next.val:
                    pre = pre.next
                temp = head.next
                head.next = temp.next
                temp.next = pre.next
                pre.next = temp
        
        return dummy.next

148. 排序链表

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路

使用归并排序，使用快慢指针找到中间结点后进行递归。

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        mid = self.getmiddle(head)
        leftHead = head
        rightHead = mid.next
        mid.next = None
        # left = self.sortList(leftHead)
        # right = self.sortList(rightHead)
        # sortMerge = self.merge(left,right)
        # return sortMerge
        return self.merge(self.sortList(leftHead),self.sortList(rightHead))

    def getmiddle(self,head):
        if not head:
            return head
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def merge(self,leftHead,rightHead):
        dummyNode = ListNode(0)
        dummyHead = dummyNode
        i,j = leftHead, rightHead
        while i and j:
            if i.val < j.val:
                dummyNode.next = i
                i = i.next
            else:
                dummyNode.next = j
                j = j.next
            dummyNode = dummyNode.next
        if i:
             dummyNode.next = i
        if j:
             dummyNode.next = j
        return dummyHead.next


if __name__ == '__main__':
    result = Solution().sortList(head)
    while result:
        print(result.val,end = ' ')
        result = result.next

179. 最大数

题目描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数。

解题思路

两层循环遍历，每一个数和之后的每一个数进行比较，交换大的数放在前面；
两个数谁应该放在前面：拼接两个字符串进行比较 a+b>b+a，则a在前面。

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if len(nums) == 0:
            return '0'
        if len(nums) == 1:
            return str(nums[0])
        
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if str(nums[i])+str(nums[j]) < str(nums[j])+str(nums[i]):
                    nums[i], nums[j] = nums[j], nums[i]
        
        return '0' if nums[0] == 0 else ''.join([str(x) for x in nums])

215. 数组中的第K个最大元素

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解题思路

思路1：利用堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质；
即子结点的键值或索引总是小于（或者大于）它的父节点。
通常堆是通过一维数组来实现的。在起始数组为 0 的情形中

父节点i的左子节点在位置 (2i+1)；
父节点i的右子节点在位置 (2i+2)；
子节点i的父节点在位置 floor((i-1)/2)。
堆的操作：在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作

最大堆调整（Min_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点；
创建最大堆（Build_Min_Heap）：将堆所有数据重新排序;
注：堆排序不是一种稳定排序。
用小根堆得办法寻找最大的K个数

用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个；
每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆。如果X比堆顶元素大；
那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质；
调整过程时间复杂度为O(logK)。全部的时间复杂度为O(N*logK)；
这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次。

堆排序

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if len(nums) < k or k <= 0:
            return 0
        res = nums[:k]
        change = True
        for i in range(k,len(nums)+1):
            if change:
                for j in range(k//2,-1,-1):
                    self.adjust(res,j,k)
                for j in range(k-1,0,-1):
                    res[j],res[0] = res[0],res[j]
                    self.adjust(res,0,j)
                change = False
            if i != len(nums) and nums[i] > res[k-1]:
                res[k-1] = nums[i]
                change = True
        return res[k-1]

    def adjust(self,res,parent,length):
        temp = res[parent]
        child = 2*parent+1
        while child < length:
            if child+1 < length and res[child+1]<res[child]:
                child = child+1
            if temp < res[child]:
                break
            res[parent] = res[child]
            parent = child
            child = 2*parent+1
        res[parent] = temp

if __name__ == '__main__':
    result = Solution().findKthLargest([3,2,3,1,2,4,5,5,6],4)
    print(result)

思路2：利用快速排序

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割左边都是比它小的数，右边都是比它大的数。
然后在按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，因此达到整个数据变成有序序列。
举例：nums = [3,2,1,5,6,4]
- 首先以nums[0]=3为基准点，设置指针left指向第一个元素(0)，right指向最后一个元素(len(nums)-1)；
- 从右至左偏移right指针，寻找到第一个比基准点3小的元素，将该元素(这里为1)赋给left指针所指的位置，此时数组为[1,2,1,5,6,4];
- 从左至右偏移left指针，寻找到第一个比基准点3大的元素，将该元素赋给right指针所指的位置，此时数组
- 不断循环步骤一二，知道left和right重合，将基准点3赋给重合位置，一轮排序结束数组为[1,2,3,5,6,4];
- 经过递归过程，最后排序结束。

**快速排序

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        
        if len(nums) < k or k <= 0:
            return 0
        
        self.Qsort(nums, 0, len(nums)-1)
        return nums
    
    def Qsort(self, nums, left, right):
        if left < right:
            index = self.division(nums, left, right)
            self.Qsort(nums, left, index-1)
            self.Qsort(nums, index+1, right)
    
    def division(self, nums, left, right):
        base = nums[left]
        while left < right:
            
            while right > left and nums[right] >= base:
                right -= 1
            nums[left] = nums[right]
            while left < right and nums[left] <= base:
                left += 1
            nums[right] = nums[left]
        nums[left] = base
        return left

思路3：归并排序

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        
        if len(nums) < k or k <= 0:
            return 0
        
        res = self.dfs(nums)
        return res[-k]
    
    def dfs(self, nums):
        if len(nums) <= 1:
            return nums
        mid = len(nums)//2
        left = self.dfs(nums[:mid])
        right = self.dfs(nums[mid:])
        
        return self.merge(left, right)
    
    def merge(self, left, right):
        res = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                j += 1
        
        if i < len(left):
            res += left[i:]
        else:
            res += right[j:]
        
        return res

347. 前K个高频元素

题目描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

解题思路

使用桶排序算法

首先使用散列表统计数组中元素出现的频次；
接着新建len(nums)+1个桶，用于保存出现次数对应的元素；
最后，从逆序桶中取出前k个元素。

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if len(nums)<k:
            return []
        Dict = {}
        for x in nums:
            Dict[x] = Dict.get(x,0)+1
        bucket = [[] for _ in range(len(nums)+1)]
        for key, val in Dict.items():
            bucket[val].append(key)
        res = []
        for i in range(len(nums),-1,-1):
            if bucket[i]:
                res.extend(bucket[i])
            if len(res)>=k:
                break
        return res

if __name__ == '__main__':
    result = Solution().topKFrequent([1,1,1,2,2,3], 2)
    print(result)

451. 根据字符出现频率排序

题目描述

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:”tree”
输出: “eert”
解释: ‘e’出现两次，’r’和’t’都只出现一次。因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。
示例 2:

输入:”cccaaa”
输出:”cccaaa”
解释:’c’和’a’都出现三次。此外，”aaaccc”也是有效的答案。注意”cacaca”是不正确的，因为相同的字母必须放在一起。
示例 3:

输入:”Aabb”
输出:”bbAa”
解释:此外，”bbaA”也是一个有效的答案，但”Aabb”是不正确的。注意’A’和’a’被认为是两种不同的字符。

解题思路

桶排序

class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)==0:
            return ''
        Dict = {}
        for x in s:
            Dict[x] = Dict.get(x,0)+1
        bucket = ['' for _ in range(len(s)+1)]
        for key,val in Dict.items():
            bucket[val] += val * key
        res = ''
        for i in range(len(s),-1,-1):
            if bucket[i]:
                res += bucket[i]
        return res

if __name__ == '__main__':
    result = Solution().frequencySort('tree')
    print(result)