Python知识点整理（2） —— 数据结构与内置算法

数据结构与算法

内置的算法数据结构

数据结构/算法	语言内置	内置库
线性结构	list/tuple	array/collections.nametuple
链式结构		collections.deque（双端队列)
字典结构	dict	collections.Counter（计数器）/orderedDict（有序字典）
集合结构	set/frozenset
排序算法	sorted
二分算法		bisect模块
堆算法		heapq模块
缓存算法		functools.lru_cache(Least Recent Used, python3)

collections模块

• namedtuple()
• deque 提供了一个双端队列
• Counter
• OrderedDict(记录key插入的顺序 ，使用了循环双链表实现 )
• defaultdict

python dict 底层结构

• 哈希表
• 时间复杂度 o（1）
• 使用二次探查解决哈希冲突问题

哈希冲突

• 链接法
• 探查法

哈希表扩容

python list/tuple区别

• 都是线性结构
• list可变对象，tuple保存的引用不可变（指的是没法替换掉这个对象，但如果引用指向的是可变对象，是可以修改这个引用指向的可变对象的）
• list没法作为字典的key，tuple可以（可变对象不可hash）

LRU cache

• Least Recently Used替换掉最近最少使用的对象
• 当缓存空间不够的时候需要一种方式剔除key
• 常见的有LRU, LFU等
• LRU通过使用一个循环双端队列不断把最新访问的key放到表头实现

实现LRU Cache

• dict + collections.OrderedDict实现
• dict来当作k/v键值对的缓存
• orderdict用来实现更新最近访问的key

常考算法

排序算法	最差时间分析	平均时间复杂度	稳定性	空间复杂度
冒泡排序	O(N^2)	O(N^2)	稳定	O(1)
选择排序	O(N^2)	O(N^2)	不稳定	O(1)
插入排序	O(N^2)	O(N^2)	稳定	O(1)
快速排序	O(N^2)	O(Nlog2N)	不稳定	O(log2N) ~O(N)
堆排序	O(N^log2N)	O(Nlog2N)	不稳定	O(1)

排序算法的稳定性

• 相同大小的元素排序之后依然保持相对位置不变，就是稳定的

快速排序

• 退化？？？？
• 分治法（devide and conquer）

def QuickSort(array):
	if len(array) <= 1: # 递归出口
		return array
	
	pivot_index = 0 # 选择第一个元素作为主元
	pivot = array[pivot_index]
	pivot_left = [
		i for i in array[pivot_index+1:] if array[i]<=pivot	
	]
	pivot_right = [
		i for i in array[pivot_index+1:] if array[i] > pivot
	]
	return QuickSort(pivot_left) + [pivot] + QuickSort(pivot_right)

归并排序

def MergeSortedList(sorted_a, sorted_b):
	len_a, len_b = len(sorted_a), len(sorted_b)
	a, b = 0, 0
	merge_list = []
	while a < len_a and b < len_b:
		if sorted_a[a] <= sorted_b[b]:
			merge_list.append(sorted_a[a])
			a += 1
		else:
			merge_list.append(sorted_b[b])
			b += 1
	# 把多余的放到有序数组里面
	if a < len_a:
		merge_list.extend(sorted_a[a:])
	else:
		merge_list.extend(sorted_b[b:])
	return merge_list

def MergeSort(array):
	# 定义递归出口
	if len(array) <= 1:
		return array
	
	mid = len(array) / 2
	left_array = MergeSort(array[:mid])
	right_array = MergeSort(array[mid:])
	return MergeSortedList(left_array, right_array)

堆排序

• 借助heapq模块快速实现

def HeapSort(array):
	from heapq import heappush, heappop
	items = []
	for val in array:
		heappush(items, val)
	return [heappop(items) for i in range(len(array))]

二分查找

• 需要注意边界情况的判定

def BinarySearch(sorted_array, target):
	if not sorted_array:
		return -1
	
	begin, end = 0, len(sorted_array)-1
	while begin <= end:
		mid = (begin + end) / 2
		if sorted_array[mid] == target:
			return mid
		if sorted_array[mid] < target: # 要去右边找
			begin = mid + 1
		else: # 要去左边找
			end = mid - 1
	return -1

常考数据结构

链表

队列

• collection.deque双端队列 （左右边都可以）

from collections import deque
class Queue:
	def __init__(self):
		self.itmes = deque()
	def append(self, val):
		return self.itmes.append(val)
	def pop(self):
		return self.items.popleft()
	def empty(self):
		return len(self.items) == 0

• 用list实现
  • 后面加方便
  • 前面，效率不如deque

栈

• collections.deque实现
• list实现

用两个栈实现一个队列
min stack

字典&集合

• 底层：哈希表
• 哈希函数快速定位一个元素
• 不断加入元素会引起哈希表重新开辟空间，拷贝元素到新数组

哈希表解决冲突

• 链接法：key冲突以后使用链表填充相同的key元素
• 开放寻址法： 冲突后根据一种方式（二次探查）寻找下一个客用的槽

二叉树

• 先序：根、左、右
• 中序：左、根、右
• 后序：左、右、根

class BinTreeNode(object):
	def __init__(self, data, left=None, right=None):
		self.data, self.left, self.right = data, left, right
class BinTree(object):
	def __init__(self, root=None):
		self.root = root
	def preorder_trav(self, subtree):
		"""先序遍历"""
		if subtree is not None:
			print (subtree.data) # 根
			self.preorder_trav(subtree.left) # 左子树
			self.preorder_trav(subtree.right) # 右子树
	def inorder_trav(self, subtree):
		"""中序遍历"""
		if subtree is not None:
			self.inorder_trav(subtree.left) # 左子树
			print (subtree.data) # 根
			self.inorder_trav(subtree.right) # 右子树

堆

• 完全二叉树
  • 最大堆：非叶子结点v，v的值都比他的两个孩子大（支持pop获取最大元素）
  • 最小堆：非叶子结 点v，v的值都比他的两个孩子小（支持pop获取最小元素）
• 常见问题：topK问题（找出最大的k个）

import heapq
class TopK:
	"""
	获取最大的k个元素，应该用最小堆实现
	思路：
	1. 原始数组的前k个元素构成一个最小堆
	2. 从第k+1个元素开始：
		如果当前元素的值<=堆根节点的值（当前堆中的最小值），pass
		如果大于的话，就用这个元素的来代替当前的根节点，并调整堆
	"""
	def __init__(self, iterable, k):
		self.minheap = []
		self.capacity = k
		self.iterable = iterable
	def push(self, val):
		if len(self.minheap)>= self.capacity:
			min_val = self.minheap[0]
			if val < min_val:
				pass
			else:
				heapq.heapreplace(self.minheap, val)
		else:
			heap.heappush(self.minheap, val)
	def get_topk(self):
		for val in self.iteralbe:
			self.push(val)
		return self.minheap