目录
  1. 1. 前言
    1. 1.1. 215-数组中的第k个最大元素
      1. 1.1.1. 题目
      2. 1.1.2. 题解
    2. 1.2. 347-前k个高频元素
      1. 1.2.1. 题目
      2. 1.2.2. 题解
    3. 1.3. 451-根据字符出现频率排序
      1. 1.3.1. 题目
      2. 1.3.2. 题解
    4. 1.4. 75-颜色分类
      1. 1.4.1. 题目
      2. 1.4.2. 题解
leetcode-排序1

前言

回顾完八大排序,刷一下leetcode中排序的经典题目。

  • 215-数组中的第k个最大元素
  • 347-前k个高频元素
  • 451-根据字符出现频率排序
  • 75-颜色分类

215-数组中的第k个最大元素

题目

  • 难度:中等

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

  • 示例:

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

    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4
  • 说明:你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

题解

  • 思路:Topk问题 和 kth 问题,可以使用快排和堆排序。
  • 快排步骤
    • 挑选基准值:从数列中挑出一个元素,称为"基准"(pivot);
    • 分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成;
    • 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
#快排递归
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def partition(arr, low, high):
i = low - 1 #最小元素索引
pivot = arr[high]
for j in range(low, high):
# 当前元素小于或等于pivot
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

def quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
return arr

if not nums or not k or k > len(nums):
return
quickSort(nums, 0, len(nums) - 1)
return nums[-k]
#快排非递归
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def partition(arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSort(arr, low, high):
if len(arr) < 2:
return arr
stack = [len(arr) - 1, 0]
while stack:
low = stack.pop()
high = stack.pop()
index = partition(arr, low, high)
if low < index - 1:
stack.append(index - 1)
stack.append(low)
if high > index + 1:
stack.append(high)
stack.append(index + 1)
return arr
if not nums or not k or k > len(nums):
return
quickSort(nums, 0, len(nums) - 1)
return nums[-k]
  • 时间复杂度:O(n2)O(n^2),最坏情况,存在倒序数组,此时递归树画出来是链表。

  • 空间复杂度:O(n)O(n)

  • 堆排序步骤:(大顶堆升序)

    • 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆);
    • 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素;
    • 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素;
    • 如此反复进行交换、重建、交换,直到整个序列有序。
#堆排序-大顶堆
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
for i in range(n, -1, -1):
heapify(arr, n, i)
for i in range(n -1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
if not nums or not k or k > len(nums):
return
heapSort(nums)
return nums[-k]
  • 时间复杂度:O(Nlogk),大小为 k 的堆中添加元素的时间复杂度为 O(logk),我们将重复该操作 N 次,故总时间复杂度为O(Nlogk)。
  • 空间复杂度:O(k),存储堆元素
  • 在 Python 的 heapq 库中有一个 nlargest 方法,具有同样的时间复杂度,能将代码简化到只有一行。
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
return heapq.nlargest(k, nums)[-1]
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
return sorted(nums)[-k]

347-前k个高频元素

题目

  • 难度:中等

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

  • 示例

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

    输入: nums = [1], k = 1
    输出: [1]
  • 提示:

    • 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
    • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
    • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
    • 你可以按任意顺序返回答案。

题解

class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or not k or k > len(nums):
return

dict = {}
for num in nums:
if num not in dict:
dict[num] = 1
else:
dict[num] += 1
dict = sorted(dict.items(), key = lambda items:items[1], reverse = True)

res = []
for key, value in dict:
res.append(key)
return res[:k]
  • 时间复杂度:O(Nlogk),遍历一遍数组O(N),N为数组长度,字典排序时间复杂度:O(Nlogk),k是k个键值对数

  • 空间复杂度:O(K),dict存储键值对K,res存储key值K个,O(2K)。

  • 思路:桶排序

    • 当桶个数很大的时候,就是计数排序。基于桶排序的计数排序的过程,第一步就是需要统计原数组中各个数字的出现的频率,使用的方法是,先遍历出原始数组,找到最大值maxValue和最小值minValue,开辟maxValue-minValue大小的计数器数组counter。如nums =[2, 1, 3, 1, 5], counter = [2, 1, 1, 0, 1] , counter[0] 表示值 0 + minValue = 1 出现了2次。(1出现2次)。
    • 这和上述哈希表统计各个数字出现的次数效果一样,时间复杂度和空间复杂度都是一样的,哈希表效果相对较好,原因是:当maxValue-minValue过大时,会产生内存浪费。
    • 统计完各个数字出现的频率后,创建一个数组,将频率作为数组下标,对于出现频率不同的数字集合,存入对应的数组下标即可。时间复杂度上优化了对字典的排序。
  • 根据value获取key的三种方法:
  • python常用的字典操作:
    • dict.values():Python 字典(Dictionary) values() 函数以列表返回字典中的所有值。
    • dict.items():Python 字典(Dictionary) items() 函数以列表返回可遍历的(键, 值) 元组数组。
  • append和extend的区别:
    • https://www.jianshu.com/p/d83053742cb9
    • https://blog.csdn.net/dpengwang/article/details/79102305
    • append:简单的说,append是直接在list后面添加元素,该元素是什么样就添加什么样。如a = [1,2,3],b=[4],a.append(b)–>[1,2,3[4]]
    • extend:extend是扩展,在原有List上进行修改,没有返回值,可以扩展不同类型的变量,并将其内容以List变量的形式加入到原List中。如果extend的是字符串,则字符串会被拆分成字符数组,如果extend的是字典,则字典的key会被加入到List中。
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or not k or k > len(nums):
return
dict = {}
for num in nums:
if num not in dict:
dict[num] = 1
else:
dict[num] += 1

max_time = max(dict.values()) #获取出现的最大次数
TongList = [[] for i in range(max_time + 1)] #根据最大次数生成桶
for key, value in dict.items():
TongList[value].append(key) #将索引value放入key对应的字典索引 eg1:[[],[3],[2],[1]]

res = []
for i in range(max_time, 0, -1): #按桶索引排序
if TongList[i]:
res.extend(TongList[i]) #如果是append,eg1:[[1],[2]]
if len(res) >= k:
return res[:k]
  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

  • 思路:https://leetcode-cn.com/problems/top-k-frequent-elements/solution/yi-xing-python3dai-ni-zou-jin-counterlei-by-jimmy0/

    • 统计每个数的频率,输出最大的几个,这完全迎合了Python中的Counter类,调用其的几个方法即可。
    • 什么是Counter?
      • Counter 是一个在collections包里的类,正如其名,是一个用于计数的工具。
      • 我们可以用Counter(nums)这样的构造函数构造一个Counter类,其中nums是一个列表。
      • 构造好的Counter实例可以看作一个字典,键是nums的每一项,值是它的出现次数。
      • 如果上面的叙述让你感到很混乱的话,我不妨举个例子。
        • 如果一个列表a = [1,1,3,4,3],你想要统计每项的出现次数,那么你使用b = Counter(a),那么这时候b就像一个这样的字典{1:2,3:2,4:1},表示数字1出现了2次,数字3出现了2次,数字4出现了1次。
        • 还是很好理解的吧?
        • 可是题目里要我们输出的是最多的K项
        • 这时候可以应用Counter的一个函数,most_common(k)
        • 这个函数就是返回最多出现的K项
        • 但是返回的形式是一个元祖列表,类似[(1,2),(3,2),(4,1)]的形式
        • 我们只需要键也就是第一项,所以要使用列表生成式处理一下即可。
from collections import Counter

class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or not k or k > len(nums):
return
return [i[0] for i in Counter(nums).most_common(k)]

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'被认为是两种不同的字符。

题解

  • 思路:本题和347题思路一致,只是在处理返回结果时操作不同:
    • 哈希表+字典排序:
      • 将字符串转为list,遍历一遍list,获取每个字符出现的频率
      • sorted函数倒序排序字典
      • 初始化list保存字符出现频率按降序排序后的结果
      • 遍历降序排序好的字典的键值对,当value(频率)≥1时,说明该字符(key)出现≥1次,那就append value次对应的key。
      • 将list转为字符串返回即可。
      • 时间复杂度:O(nlogn)
      • 空间复杂度:O(n)
    • 桶排序:
      • 将字符串转为list,遍历一遍list,获取每个字符出现的频率
      • 获取最大出现次数
      • 根据最大出现次数生成桶
      • 将索引value放入key对应的字典索引
      • 初始化res保存字符出现频率按降序排序后的结果
      • 按桶索引i倒排序,如果对应桶索引有值,就遍历桶中的元素j,把每个元素逐一添加i次。
      • 将list转为字符串
      • 时间复杂度:O(n),O(max_time^2 * len(TongList) )
      • 空间复杂度:O(n)
#哈希表 + 字典排序
class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
s = list(s)
dict = {}
for i in s:
if i not in dict:
dict[i] = 1
else:
dict[i] += 1
dict = sorted(dict.items(), key = lambda items: items[1], reverse = True)

res = []
for key, value in dict:
while value >= 1:
res.append(key)
value -= 1
return ''.join(res)
class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
s = list(s)
dict = {}
for i in s:
if i not in dict:
dict[i] = 1
else:
dict[i] += 1

max_times = max(dict.values())
TongList = [[] for i in range(max_times + 1)]

for key, value in dict.items():
TongList[value].append(key)

res = []
for i in range(max_times, 0, -1):
if TongList[i]:
for j in TongList[i]:
for n in range(0, i):
res.append(j)
return ''.join(res)

75-颜色分类

题目

  • 难度:中等

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

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

  • 示例:

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

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

题解

  • 思路:一次遍历和两次遍历

    • 两次遍历(非原地):(如果没有要求原地处理数组,那是可以的,注意审题,题目要求的是原地处理!因为没注意审题,纠结了很久)

      • 用哈希表统计每个元素出现的个数
      • 按照key值排序
      • 初始化数组res保存返回结果
      • 按照排好序的键值对填充数组res
    • 两次遍历(原地):

      • 初始化数组res,由于最多只有3种颜色,res长度为3。
      • 统计每个数字出现的次数,下标对应数字,数组值对应次数
      • 初始化指针j指向nums第一个位置
      • 依次读取每个数字出现的次数,对nums进行重写
    • 一次遍历:

      • 类似”冒泡“思想,遇到小的值就上浮到顶部,遇到大的值就下沉到底部。

      • 需要使用三个指针,p0用来确定0的右边界、p2用来确定2的左边界、curr用来当前元素

      • 沿着数组移动 curr 指针,若nums[curr] = 0,则将其与 nums[p0]互换;若 nums[curr] = 2 ,则与 nums[p2]互换。

      • 算法步骤

        • 初始化0的最右边界:p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
    • 初始化2的最左边界 :p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.

      • 初始化当前考虑的元素序号 :curr = 0.
    • While curr <= p2 :

      • 若 nums[curr] = 0 :交换第 curr个 和 第p0个 元素,并将指针都向右移。
        • 若 nums[curr] = 2 :交换第 curr个和第 p2个元素,并将 p2指针左移 。
      • 若 nums[curr] = 1 :将指针curr右移。
#两次遍历(原地)
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""

color = [0] * 3

#统计每个数字出现的次数,下标对应数字,数组值对应次数
for i in nums:
color[i] += 1

j = 0 #初始化指针j指向nums第一个位置

#依次读取每个数字出现的次数,对nums进行重写
for m in range(3):
for n in range(color[m]):
nums[j] = m
j += 1
  • 时间复杂度:O(m * n),m为元素种类数,n为每种元素的出现的次数
  • 空间复杂度:O(m)
#一次遍历
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""

# 对于所有 idx < p0 : nums[idx < p0] = 0
# curr是当前考虑元素的下标
p0 = curr = 0
# 对于所有 idx > p2 : nums[idx > p2] = 2
p2 = len(nums) - 1

while curr <= p2:
if nums[curr] == 0:
nums[p0], nums[curr] = nums[curr], nums[p0]
p0 += 1
curr +=1
elif nums[curr] == 2:
nums[curr], nums[p2] = nums[p2], nums[curr]
p2 -= 1
else:
curr += 1
  • 时间复杂度:O(n),遍历一遍数组,n为数组长度
  • 空间复杂度:O(1),额外使用三个指针
文章作者: Lesy
文章链接: https://lesylin.com/2020/06/26/leetcode-%E6%8E%92%E5%BA%8F1/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment