开篇第一章,介绍一下常见的数据结构,之后的章节介绍常见的算法解题框架
1、数组
? ? ? ? 优点:内存连续,查找效率高,为O(1)
????????缺点:内存连续,因此插入/删除时间复杂度高,为O(n)
2、链表
????????优点:内存不连续,插入/删除时间复杂度低,为O(1)
????????缺点:内存不连续,因此查找时间复杂度高,为O(n)
3、栈Stack
????????先入后出(FILO);可以通过数组/链表实现;两个栈,一个入栈,一个出栈,可以模拟队列操作。
4、队列Queue
????????先入先出(FIFO);可以通过数组/链表实现;常用于消息队列;
5、优先队列PriorityQueue
????????先入按照优先级出(FIFO);可以通过堆Heap(Binary、Binomial、Fibonacci)/二叉搜索树(Binary Search Tree)实现,一般不会考如何实现,现在优先队列都纳入了标准库中,了解实现机制即可;
6、堆Heap
7、映射(Map)&集合(Set)
映射(Map)&集合(Set)一般由哈希/二叉树实现,需要先了解HashTable & Hash Function & Hash Collisions。哈希: key经过Hash Function 处理后,O(1)的时间复杂度在HashTable(一般维数组) 找到数据所在的位置。Hash?Collisions的一种解决方式为拉链法:冲突后在HashTable 元素后面挂链表来存放位置冲突的元素。
List & 映射(Map) & 集合(Set)的区别:List 元素可重复,一般用数组/链表实现;?映射(Map)是key/value映射关系,一般用哈希(O(1))/树(O(logn))实现,比数组查找效率高;集合(Set)与List 比,元素不可重复,一般用哈希(O(1))/树(O(logn))实现,比数组查找效率高;
映射(Map)常用实现有两种:HashMap、TreeMap,查找数据时间复杂度为O(1),但是数据是无序存放的;集合(Set)常用实现有两种:HashSet、TreeSet,查找数据时间复杂度为O(logn),但是数据是有序存放的;
8、