专项学习算法之排序

（注意：以下题目来源牛客）

单链表的排序(简单)

给定一个节点数为n的无序单链表，对其按升序排序。 数据范围：

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        # write code here
        pass 
str1 = list(map(int, input()[1 : -1].split(',')))
str1 = sorted(str1) 
print('{' + ','.join(list(map(str, str1))) + '}')

最小的K个数(中等)

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。 数据范围：

数组中每个数的大小

要求：空间复杂度 O(n) ，时间复杂度 O(nlogn)

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        list=[]
        if len(tinput)<k:
            return list
        else:
            tinput.sort()
            return tinput[:k]

合并区间(中等)

给出一组区间，请合并所有重叠的区间。 请保证合并后的区间按区间起点升序排列。

数据范围：区间组数

，区间内 的值都满足

要求：空间复杂度 O(n)，时间复杂度 O(nlogn) 进阶：空间复杂度 O(val)，时间复杂度O(val)

class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        # write code here
        if not intervals:
            return []
        intervals.sort(key=lambda x:x.start)
        res = []
        res.append(intervals[0])
        for i in range(1,len(intervals)):
            last = res[-1]
            cur = intervals[i]
            if last.end<cur.start:
                res.append(cur)
            else:
                last.end = max(last.end, cur.end)
        return res

最大数(中等)

给定一个长度为n的数组nums，数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出。

数据范围：

进阶：时间复杂度O(nlogn) ，空间复杂度：O(n)

基本思路： 1、每次将相邻的两个字符串拼接，然后比大小，从而确定相邻的两个字符串是否交换位置。 2、如果排序好的数组第一个元素就是“0”，那么结果直接返回字符串“0”。 3、如果第一个元素不是“0”，直接从头到尾拼接返回就好了。

class cmp(str):
    def __lt__(x, y):
        # 子字符串正反拼接的结果判断（注意是字符串）
        return x+y > y+x
class Solution:
    
    def solve(self , nums: List[int]) -> str:
        # write code here
        # 1. 转换为字符串
        nums = [str(n) for n in nums]
        # 2. 排序
        # 相邻两个字符串正反拼接，将大数放在最前面
        nums = sorted(nums, key=cmp)
        if nums[0] == '0':
            return '0'
        else:
            return ''.join(nums)

栈和排序（中等）

给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈

你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列

排列：指 1 到 n 每个数字出现且仅出现一次

数据范围：

排列中的值都满足

进阶：空间复杂度 O(n) ，时间复杂度 O(n)

设计思想： 1、因为要满足字典序最大，所以第一个出栈的一定是n，所以我们需要定义一个n来控制元素的出栈顺序； 2、为了满足字典序最大我们还得知道哪些元素已经入了栈，因为n-1有可能在n之前就入了栈了， 所以我们需要编辑数组来知道哪些较大的数据入栈（因为这些数据可以提前出栈）， 那么我们就遍历数据通过n和标记数组来空竹出战的顺序； 3、如果数据遍历完，栈还没有空，我们只能将栈中元素全部弹出。

class Solution:
    def solve(self , a: List[int]) -> List[int]:
        # write code here
        s = [] #定义一个栈用来存储数据(我们用数组来模拟)
        n  = len(a)
        res = []#用来返回结果
        vis = [0] *(n+1)#用来标记哪个数字出现过
        for i in a:
            s.append(i)#压入栈
            vis[i] = 1#压入一个数就把对应的数字标记为1
            while n and vis[n]: n-=1#检测现有栈中有多少个数出现了就是较大的哪些数出现了（从大到小）
            while s and n <= s[-1]:
                #然后将栈中>=n的元素出栈
                res.append(s[-1])
                s.pop()
        #如果栈没为空就按照栈中原样直接出栈
        while s:
            res.append(s[-1])
            s.pop()
        return res

数据流中的中位数(中等)

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

数据范围：数据流中数个数满足

大小满足

进阶： 空间复杂度 O(n) ， 时间复杂度 O(nlogn)

堆排序思想： 中位数为一个数列的中间两个或一个，也即中位数将数列分成了较小的部分和较大的部分。我们可以维护两个堆，分别是大顶堆min，用于存储较小的值，其中顶部最大；小顶堆max，用于存储较小的值，其中顶部最小，则中位数只会在两个堆的堆顶出现。我们可以约定奇数时取大顶堆的顶部值，偶数时取两堆顶的平均值，则可以发现两个堆的数据长度要么是相等的，要么奇数时大顶堆会多一个。 每次输入的数据流先进入大顶堆排序，然后将小顶堆的最大值弹入大顶堆中，完成整个的排序。但是因为大顶堆的数据不可能会比小顶堆少一个，因此需要再比较二者的长度，若是小顶堆长度小于大顶堆，需要从大顶堆中弹出最小值到大顶堆中进行平衡。

import heapq
class Solution:
    def __init__(self):
        self.maxheapq=[]  # 大堆：存放小于中位数的元素（奇数时包含中位数）
        self.minheapq=[]  # 小堆：存放大于中位数的元素
    def Insert(self, num):
        # write code here
        if len(self.maxheapq)==len(self.minheapq):
            heapq.heappush(self.minheapq,-heapq.heappushpop(self.maxheapq,-num))
        else:
            heapq.heappush(self.maxheapq,-heapq.heappushpop(self.minheapq,num))
    def GetMedian(self):
        # write code here
        if len(self.maxheapq)==len(self.minheapq):
            return (self.minheapq[0]-self.maxheapq[0])/2
        return self.minheapq[0]

链表的奇偶重排

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。 注意是节点的编号而非节点的数值。

数据范围：节点数量满足

节点中的值都满足

要求：空间复杂度 O(n)，时间复杂度 O(n)

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        evenHead = head.next
        odd, even = head, evenHead
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = evenHead
        return head