常见数据结构
线性数据结构（按顺序具有数据元素的数据结构）：数组，堆栈，链表（单链表 双链表），队列
非线性数据结构（以非顺序方式存储数据）：树，图，表。
时间复杂度和空间复杂度
时间复杂度执行这个算法耗费的时间
空间复杂度是指执行这个算法所需要的内存空间
1.数组
在内存内连续的存储
查找十分快捷，a[k]_address = base_address + k * type_size k从0开始
下标不从1开始，如果从1开始，需要做一次减法 k-1，每次都要
但是不利于插入或者删除元素，需要对元素进行移动
2.单链表
不需要连续的存储空间，插入或者删除一个节点方便，但是删除的时候需要先查找，也是会耗时，每个节点不仅要存储自己节点的值，还需要存储下一个节点的地址，比数组的存储空间需要更大。
循环单链表，尾指针指向头节点
image.png
package main
import "fmt"
func main() {
//构建一个单链表
result:=GetNewListNode(6)
// 在链表头部增加一个元素
result=AddOneNodeBeforeHead(result,9)
result.Println()
// 在链表尾部增加一个元素
result.AddOneNodeFromLast(10)
result.Println()
fmt.Println("链表长度:",result.GetListLength(),"\n")
//链表反转
result= result.ListRever()
result.Println()
//找出链表的中间元素
//删除链表的倒数第n个元素
//移除链表的某个元素
//链表有换头操作需要返回新链表
//result.Println()
}
type ListNode struct {
Val int
Next *ListNode
}
// 新增一个指定长度的链表
func GetNewListNode(max int)*ListNode{
result:=&ListNode{
Val:max,
}
for i:=max-1;i>=1;i--{
node:=&ListNode{
Val:i,
}
node.Next=result
result=node
}
return result
}
// 链表头部增加一个元素
func AddOneNodeBeforeHead(n *ListNode,val int)*ListNode{
node:=&ListNode{Val:val}
node.Next=n
return node
}
// 尾部增加一个节点
func (list *ListNode) AddOneNodeFromLast(val int){
for list!=nil{
if list.Next==nil{
list.Next=&ListNode{Val:10}
return
}
list=list.Next
}
}
// 打印链表的值
func (n *ListNode) Println(){
for n!=nil{
fmt.Println(n.Val)
n=n.Next
}
fmt.Println("\n")
}
//获取链表长度
func (list *ListNode) GetListLength()int{
n:=0
for list!=nil{
n++
list=list.Next
}
return n
}
// 链表反转
func (list *ListNode) ListRever()*ListNode{
curl:=list
var pre *ListNode=nil
for curl!=nil{
pre,curl,curl.Next=curl,curl.Next,pre
}
return pre
}
//递归链表反转
func ListRever1(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newList := ListRever1(head.Next)
// 改变 1，2节点的指向。
// 通过 head.next获取节点2
t1 := head.Next
// 让 2 的 next 指向 2
t1.Next = head
// 1 的 next 指向 null.
head.Next = nil
return newList
}
// 链表反转(迭代法)
//定义三节点，名字前中后，中如不为空，继续遍历表，
//前中后换位，同时往后移动，最后返回前，得到反转表
func (list *ListNode) ListRever2()*ListNode{
var pre *ListNode
middle:=list
var next*ListNode
var pre *ListNode=nil
for middle!=nil{
next=middle.Next
middle.Next=pre
pre=middle
middle=next
}
return pre
}
// 快慢节点法查找中间节点
func (list *ListNode) GetMiddleNode() (middle []int){
fast:=list
slow:=list
for slow!=nil{
//奇数个节点
if fast.Next==nil{
return append(middle,slow.Val)
}
//偶数个节点
if fast.Next!=nil&&fast.Next.Next==nil{
return append(middle,slow.Val,slow.Next.Val)
}
slow=slow.Next
fast=fast.Next.Next
}
return middle
}
// 删除元素，以当前节点是否为nil为循环结束条件
func (head *ListNode) DeleteNodeByVal(val int)*ListNode{
// 构建一个虚拟节点
newHead := &ListNode{0,head}
pre, cur := newHead, head
for cur != nil {
if cur.Val == val {
pre.Next = cur.Next
break
}
pre = cur
cur = cur.Next
}
return newHead.Next
}
// 删除一个节点 以下一个元素是否为nil为循环条件。找到要删除节点的前一个节点，修改它的后继指针
func (head *ListNode) DeleteNodeByVal11(val int){
//删除第一个
if head.Val==val{
head=head.Next
return
}
pre:=head
for pre.Next != nil {
if pre.Next.Val == val {
pre.Next = pre.Next.Next
break
}
pre = pre.Next
}
return
}
// 增加一个环
func (n *ListNode) AddOneCycle(){
head:=n
var pre*listNode=nil
for n!=nil{
if n.Next==nil{
// 来到尾部
// 最后一个元素指向前一个元素
n.Next=pre
return
}
pre=n
n=n.Next
}
}
//检测链表中是否有环 快慢指针法，类似环形跑到，两个人在上面跑步，总有会相遇的时候，相遇时两个人的位置一样
func (n *ListNode) HasCycle()bool{
fast:=n
slow:=n
for fast!=nil&&fast.Next!=nil{
fast=fast.Next.Next
slow=slow.Next
if slow==fast{
return true
}
}
return false
}
//足迹法找环，存在的话就用map记录一次这个指针
func LinkedLoopDetection1(node *ListNode) bool {
if node == nil || node.Next == nil {
return false
}
nodeMap := make(map[*ListNode]bool, 0)
for node != nil && node.Next != nil {
if _,ok:=nodeMap[node] ;ok {
return true
} else {
nodeMap[node] = true
}
node=node.Next
}
return false
}
2.2删除倒数第n个节点
先找到要删除节点的前一个节点，也就是倒数第n+1个节点
if head==nil{
return head
}
length:=0
temp:=head
for temp!=nil{
length++
temp=temp.Next
}
count:=0
del:=length-n+1 //倒数第n个，就是正数第length-n+1
if del==0{
return head.Next
}
tmp:=head
for tmp!=nil{
count++
// 找到要删除元素的前一个元素，将这个元素的next节点指向要删除节点的下一个节点
if count==(del-1){
tmp.Next = tmp.Next.Next
break
}
tmp = tmp.Next
}
return head
// 快慢指针 快指针先走n
func removeFromEnd(head *ListNode, n int) *ListNode {
if head==nil{
return head
}
//构建虚拟节点，防止删除头结点时找不到
newHead:=&ListNode{Value:-1,Next:head}
fast:=newHead
slow:=newHead
i:=0
for fast!=nil{
if i<=n{
fast=fast.Next
i++
}else{
slow= slow.Next
fast=fast.Next
}
}
slow.Next=slow.Next.Next
//剔除虚拟节点
return newHead.Next
}
2.5 两个有序链表合并
2.6 两个无环有序链表是否相交，如果有返回交点
1.空间复杂度为O(n),时间复杂度也是O(n) // 使用map，判断另一个链表的地址
2.空间复杂度为O(1),时间复杂度是O(n) // 先计算出两个链表的长度，判断尾节点是否相同，不相同肯定不相交，长的先走差的长度步数，然后再一起走，判断节点的地址是否相同
func NoLoop(headA, headB *ListNode) *ListNode {
//1.先判断尾节点是否相同，计算两个链表的长度length1 length2
if headA==nil||headB==nil{
return nil
}
n1:=headA
n2:=headB
length:=0
for n1.Next!=nil{
length++
n1=n1.Next
}
for n2.Next!=nil{
length--
n2=n2.Next
}
// 2.尾节点不相等，一定不相交
if n1!=n2{
return nil
}
n1=headA
n2=headB
if length<0{
n1=headB
n2=headA
}
length = int(math.Abs(float64(length)))
for ;length!=0;length--{
n1=n1.Next
}
// 3.让长链表先走两个链表的差值步数，然后一起走，判断节点是否相同
for n2!=n1{
n1=n1.Next
n2=n2.Next
}
return n1
}
2.7 某个有序链表如果存在环，返回入环节点
1.空间复杂度为O(n),时间复杂度也是O(n) // 使用map，判断地址
2.空间复杂度为O(1),时间复杂度是O(n) // 快慢指针
func detectCycle(head *ListNode) *ListNode {
if head==nil||head.Next==nil||head.Next.Next==nil{
return nil
}
//快慢指针找到相遇的节点，慢指针不动，
f:=head.Next.Next
s:=head.Next
for f!=s{
if f.Next==nil||f.Next.Next==nil{
return nil
}
f=f.Next.Next
s=s.Next
}
//快指针从头开始走，当快慢指针相等时，即是入口节点
f=head
for f!=s{
f=f.Next
s=s.Next
}
return s
}
2.8 返回某两个链表的相交节点（分为有环和无环）
1.无环情况为2.6代码所示
2.有环有交点的情况
两个链表有环情况的可能性.png
2.1 两个链表共用一个环，环的入口一致，使用2.7的方法找到入口节点，将两个链表的结束节点为环的入口节点即可，图中左边的情况 终止条件为当前节点到了环入口节点时
2.2 如果两个链表共用一个环，环的入口不是一个，同理也是先找到两个链表的入环节点loop1和loop2,如图右边的情况
func BothLoop(headA, headB, loop1, loop2 *ListNode) *ListNode {
//1.先判断尾节点是否相同，计算两个链表的长度length1 length2
if headA == nil || headB == nil {
return nil
}
n1 := headA
n2 := headB
if loop1 == loop2 {
length := 0
for n1.Next != loop1 {
length++
n1 = n1.Next
}
for n2.Next != loop2 {
length--
n2 = n2.Next
}
// 2.尾节点不相等，一定不相交
if n1 != n2 {
return nil
}
n1 = headA
n2 = headB
if length < 0 {
n1 = headB
n2 = headA
}
length = int(math.Abs(float64(length)))
for ; length != 0; length-- {
n1 = n1.Next
}
//3.让长链表先走两个链表的差值步数，然后一起走，判断节点是否相同
for n2 != n1 {
n1 = n1.Next
n2 = n2.Next
}
return n1
} else {
//如果转回了loop1,还没遇到loop2，则说明不相交
n1 = loop1.Next
for n1 != loop1 {
if n1 == loop2 {
//返回loop1和loop2都可以
return loop1
}
n1 = n1.Next
}
return nil
}
}
func NoLoop(headA, headB *ListNode) *ListNode {
//1.先判断尾节点是否相同，计算两个链表的长度length1 length2
if headA == nil || headB == nil {
return nil
}
n1 := headA
n2 := headB
length := 0
for n1.Next != nil {
length++
n1 = n1.Next
}
for n2.Next != nil {
length--
n2 = n2.Next
}
// 2.尾节点不相等，一定不相交
if n1 != n2 {
return nil
}
n1 = headA
n2 = headB
if length < 0 {
n1 = headB
n2 = headA
}
length = int(math.Abs(float64(length)))
for ; length != 0; length-- {
n1 = n1.Next
}
//3.让长链表先走两个链表的差值步数，然后一起走，判断节点是否相同
for n2 != n1 {
n1 = n1.Next
n2 = n2.Next
}
return n1
}
func detectCycle(head *ListNode) *ListNode {
if head == nil || head.Next == nil || head.Next.Next == nil {
return nil
}
//快慢指针找到相遇的节点，慢指针不动，
f := head.Next.Next
s := head.Next
for f != s {
if f.Next == nil || f.Next.Next == nil {
return nil
}
f = f.Next.Next
s = s.Next
}
//快指针从头开始走，当快慢指针相等时，即是入口节点
f = head
for f != s {
f = f.Next
s = s.Next
}
return s
}
//主代码入口
func GetListSameNode(headA, headB *ListNode) *ListNode {
loop1 := detectCycle(headA)
loop2 := detectCycle(headB)
//无环情况
if loop1 == nil && loop2 == nil {
return NoLoop(headA, headB)
}
//有环情况， 有两种情况，如图所示
if loop1 != nil && loop2 != nil {
return BothLoop(headA, headB, loop1, loop2)
}
return nil
}
3.双链表
记录链表的前驱节点和后继节点，双链表，
循环双链链表，头尾指针相连
LRU算法链表简单实现
func main() {
lRUCache := Constructor(2)
lRUCache.put(1, 1) // 缓存是 {1=1}
lRUCache.put(2, 2) // 缓存是 {1=1, 2=2}
lRUCache.get(1) // 返回 1
lRUCache.put(3, 3) // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
fmt.Println(lRUCache.get(2)) // 返回 -1 (未找到)
lRUCache.put(4, 4) // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1) // 返回 -1 (未找到)
lRUCache.get(3) // 返回 3
lRUCache.get(4) // 返回 4
}
//LRU算法
type LRUCache struct {
size, cap int //缓存的大小和容量
cache map[int]*LinkNode //存储的key和节点的对应关系
head, tail *LinkNode //头尾节点 不存储数据，不包括在size里面
sync.Mutex
}
//双链表
type LinkNode struct {
key, val int
pre, next *LinkNode
}
func NewLinkNode(k, v int) *LinkNode {
return &LinkNode{key: k, val: v}
}
// 初始化
func Constructor(capacity int) LRUCache {
l := LRUCache{
cap: capacity,
size: 0,
cache: make(map[int]*LinkNode),
head: &LinkNode{key: 0, val: 0},
tail: &LinkNode{key: 0, val: 0},
}
l.head.next = l.tail
l.tail.pre = l.head
return l
}
// 删除一个节点
func RemoveNode(node *LinkNode) {
node.pre.next = node.next
node.next.pre = node.pre
}
// 删除尾部节点
func (this *LRUCache) RemoveTail() *LinkNode {
//尾节点不存储数据，所以取前一个节点作为有效尾节点
node := this.tail.pre
RemoveNode(node)
return node
}
func (this *LRUCache) AddHead(node *LinkNode) {
node.next = this.head.next
node.pre = this.head
this.head.next.pre = node
this.head.next = node
}
//将节点删除并移动到头部
func (this *LRUCache) MoveToHead(node *LinkNode) {
//删除节点
RemoveNode(node)
//移动到头部
this.AddHead(node)
}
func (this *LRUCache) get(key int) int {
//读取元素，被读取的放到头部去
this.Lock()
defer this.Unlock()
if node, ok := this.cache[key]; ok {
//移动到头部
this.MoveToHead(node)
return node.val
}
return -1
}
func (this *LRUCache) put(key int, value int) {
//存入元素，已经存在修改值，并移动到头部，不存在放入，并插入到头部
this.Lock()
defer this.Unlock()
if node, ok := this.cache[key]; ok {
// 存在，修改vaL
node.val = value
// 移动元素到头部
this.MoveToHead(node)
} else {
newNode := NewLinkNode(key, value)
//插入到头部
this.AddHead(newNode)
this.cache[key] = newNode
this.size++
//容量超了删除尾部元素，size减少，删除缓存key
fmt.Println("key:", key, "size:", this.size)
if this.size > this.cap {
//删除尾部元素
node := this.RemoveTail()
fmt.Println("wei bu", node.key)
this.size--
delete(this.cache, node.key)
}
}
}
4.队列
先进先出，可以用数组实现一个队列,也可以链表实现采用头插法，尾部取元素
5.栈
先进后出，可以用数组或者链表实现一个栈
应用：浏览器的前进和后退，两个栈
type Pop struct {
Arr []interface{}
}
func NewPop() *Pop {
return &Pop{Arr: make([]interface{}, 0)}
}
func (p *Pop) AddTenNumber() {
for i := 1; i <= 10; i++ {
p.AddPop(i)
}
}
func (p *Pop) OutFiveNumber() {
for i := 1; i <= 5; i++ {
p.OutPop()
}
}
// 入栈元素
func (p *Pop) AddPop(a interface{}) {
p.Arr = append(p.Arr, a)
}
func (p *Pop) Length() int {
return len(p.Arr)
}
// 出栈元素
func (p *Pop) OutPop() {
if p.Length() <= 1 {
p.Arr = nil
return
}
//fmt.Println(p.Arr)
p.Arr = p.Arr[:p.Length()-1]
}
// 打印栈的元素
func (p *Pop) PrintlnPop() {
for i := p.Length() - 1; i >= 0; i-- {
fmt.Println("a=", p.Arr[i])
}
}
6.二叉树
二叉树的遍历（递归和非递归）
6.1递归遍历
type TreeNode struct {
value int
left *TreeNode
right *TreeNode
}
func main() {
PreDigui(GetATree())
fmt.Println()
MiddleDigui(GetATree())
fmt.Println()
LastDigui(GetATree())
}
func GetATree() *TreeNode {
a := TreeNode{
value: 7,
left: nil,
right: nil,
}
b := TreeNode{
value: 6,
left: nil,
right: nil,
}
c := TreeNode{
value: 5,
left: nil,
right: nil,
}
d := TreeNode{
value: 4,
left: nil,
right: nil,
}
e := TreeNode{
value: 3,
left: &b,
right: &a,
}
f := TreeNode{
value: 2,
left: &d,
right: &c,
}
return &TreeNode{
value: 1,
left: &f,
right: &e,
}
}
//前序遍历 根左右
func PreDigui(head *TreeNode) {
if head == nil {
return
}
fmt.Print(head.value)
PreDigui(head.left)
PreDigui(head.right)
}
//中序遍历 左根右
func MiddleDigui(head *TreeNode) {
if head == nil {
return
}
MiddleDigui(head.left)
fmt.Print(head.value)
MiddleDigui(head.right)
}
//后序遍历 左右根
func LastDigui(head *TreeNode) {
if head == nil {
return
}
LastDigui(head.left)
LastDigui(head.right)
fmt.Print(head.value)
}
6.2非递归遍历
//非递归遍历 前序遍历 准备一个栈
func Pre(tree *TreeNode) {
//放入一个栈中，右左，最后打印头左右
// 采用栈实现
fmt.Print("前序非递归:")
//定义一个栈
stack := make([]*TreeNode, 0)
stack = append(stack, tree) // 入栈
for len(stack) > 0 {
tree = stack[len(stack)-1] //取栈顶元素
fmt.Print(tree.value)
stack = stack[:len(stack)-1] // 出栈
if tree.right != nil {
stack = append(stack, tree.right)
}
if tree.left != nil {
stack = append(stack, tree.left)
}
}
}
//非递归遍历 中序遍历 准备一个栈（二叉树深度优先遍历）
func Middle(head *TreeNode) {
fmt.Print("中序非递归(深度优先遍历):")
//定义一个栈
stack := make([]*TreeNode, 0)
for len(stack) > 0 || head != nil {
// 压入左边界
if head != nil {
stack = append(stack, head)
head = head.left
//没有左边界就弹出
} else {
//弹出，头结点赋值为右节点
head = stack[len(stack)-1]
fmt.Print(head.value)
stack = stack[:len(stack)-1] // 出栈
head = head.right
}
}
}
//非递归遍历 后序遍历 准备两个栈
func Last(head *TreeNode) {
// 采用栈实现 左右根
fmt.Print("后序非递归:")
//按照头左右入栈，然后再放入收集栈，最好打印收集栈
//结果收集栈
result := make([]*TreeNode, 0)
stack := make([]*TreeNode, 0)
stack = append(stack, head) // 入栈
for len(stack) > 0 {
head = stack[len(stack)-1] //取栈顶元素
stack = stack[:len(stack)-1] // 出栈
result = append(result, head) //不打印放入结果集
if head.left != nil {
stack = append(stack, head.left)
}
if head.right != nil {
stack = append(stack, head.right)
}
}
for i := len(result) - 1; i >= 0; i-- {
fmt.Print(result[i].value)
}
}
// 二叉树广度优先遍历 利用队列去实现
func LevelTravesalRange(head *TreeNode) {
fmt.Print("广度优先/层序遍历:")
queue := make([]*TreeNode, 0)
queue = append(queue, head)
for len(queue) > 0 {
head = queue[0]
fmt.Print(head.value)
queue = queue[1:]
if head.left != nil {
queue = append(queue, head.left)
}
if head.right != nil {
queue = append(queue, head.right)
}
}
}
//二叉树的最大宽度(同一层最大节点数)
func TreeMaxWidth(head *TreeNode) {
max := -1
hashMap := make(map[*TreeNode]int, 0) //所有节点所处的层数
hashMap[head] = 1
currentLevel := 1 //当前层数
currentNodes := 0 //当前层数的节点数
queue := make([]*TreeNode, 0)
queue = append(queue, head)
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:] //出栈
currentNodeLevel := hashMap[cur]
//当前节点所在层和当前层一样
if currentNodeLevel == currentLevel {
currentNodes++
} else {
//不在一层
currentLevel++
//新的层来了
currentNodes = 1
}
//节点数和最大值比较
if max < currentNodes {
max = currentNodes
}
if cur.left != nil {
hashMap[cur.left] = currentNodeLevel + 1
queue = append(queue, cur.left)
}
if cur.right != nil {
hashMap[cur.right] = currentNodeLevel + 1
queue = append(queue, cur.right)
}
}
fmt.Println("同一层最大宽度（节点数）:", max)
}
var preValue = 0
//判断一棵树是否是搜索二叉树(左边的节点小于根节点，右边的节点大于根节点)方法1
func IsSerachTree(head *TreeNode) bool {
if head == nil {
return false
}
//检查左树
is := IsSerachTree(head.left)
if !is {
return false
}
if preValue >= head.value {
return false
} else {
preValue = head.value
}
//检查右树
return IsSerachTree(head.right)
}
//非递归-判断是否是二叉搜索树 方法2
func IsSerachTree1(head *TreeNode) bool {
fmt.Print("是否是二叉搜索树:")
//定义一个栈
stack := make([]*TreeNode, 0)
preValue := 0
for len(stack) > 0 || head != nil {
// 压入左边界
if head != nil {
stack = append(stack, head)
head = head.left
//没有左边界就弹出
} else {
//弹出，头结点赋值为右节点
head = stack[len(stack)-1]
if preValue >= head.value {
return false
} else {
preValue = head.value
}
fmt.Print(head.value)
stack = stack[:len(stack)-1] // 出栈
head = head.right
}
}
return true
}
//判断树是否是完全二叉树
func WanQuanBinaryTree(head *TreeNode) bool {
if head == nil {
return false
}
var L *TreeNode
var R *TreeNode
leaf := false
queue := make([]*TreeNode, 0)
queue = append(queue, head)
for len(queue) > 0 {
head = queue[0]
fmt.Print(head.value)
queue = queue[1:]
L = head.left
R = head.right
// 遇到了非双全节点，并且当前节点不是叶子节点或 （左孩子为空，右孩子不为空）
if (leaf && !(L == nil && R == nil)) || (L == nil && R != nil) {
return false
}
if head.left != nil {
queue = append(queue, head.left)
}
if head.right != nil {
queue = append(queue, head.right)
}
if L == nil || R == nil {
//遇到了非双全节点
leaf = true
}
}
return true
}
//节点的后继节点
func HouJiJieDian(node *TreeNode) *TreeNode {
if node == nil {
return nil
}
//右节点不为空
if node.right != nil {
//往上找，知道左节点不为空
return GetNodeLeftNode(node.right)
} else {
parent := node.Parent
for parent != nil && parent.left != node { //当前节点是其父亲节点的又孩子
node = parent
parent = node.Parent
}
return parent
}
}
func GetNodeLeftNode(node *TreeNode) *TreeNode {
if node == nil {
return nil
}
for node.left != nil {
node = node.left
}
return node
}
7.查找树（基本都可以使用递归的思想）
搜索二叉树：左边的节点小于根节点，右边的节点大于根节点
完全二叉树：除了每个节点都有
满二叉树：每一层的节点数都是最大节点数
平衡二叉树：当且仅当两个子树的高度差不超过1时，这个树是平衡二叉树。（同时是排序二叉树）
两个节点最近的共同祖先节点：
1.可以用一个map，记录节点A的祖先节点，遍历查找另一个节点的祖先节点，判断是否在map中，最先找到的那个节点就是最近祖先节点
后继节点：中序遍历顺序的节点的前后关系，DBACDE
D的后继节点是B，B的后继节点是A
广度优先遍历和深度优先遍历（中序）
8.排序算法
8.1冒泡 O(n的平方)
func BubbleSort(a []int){
aLen:=len(a)
for i:=0;i<aLen;i++{
for j:=0;j<aLen-i-1;j++{
//相邻元素做比较
if a[j]>a[j+1]{
a[j],a[j+1]=a[j+1],a[j]
}
}
}
}
8.2 选择排序 O(n的平方)
func SelectSort(a []int){
aLen:=len(a)
for i:=0;i<aLen;i++{
minIndex:=i
for j:=i+1;j<aLen;j++{
if a[j]<a[minIndex]{
minIndex=j
}
}
// 交换比第i个位置小的值
if minIndex!=i{
a[i],a[minIndex]=a[minIndex],i
}
}
}
8.3 插入排序 O(n的平方)
func InsertSort(arr []int) {
arrcount := len(arr)
if arrcount < 2 {
return
}
for i := 1; i < arrcount; i++ { //0-i范围上有序
//将j和左边的数一个个对比,跳出条件是j不能小于等于0，
//并且大于它左边的数。因为它左边的数都已排好序
for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
arr[j], arr[j-1] = arr[j-1], arr[j]
}
}
}
8.4 归并排序（递归合并）
//先把左侧的元素按照递归排好序，再把右边的元素按照递归排好序
//最后将左边和右边排好序的部分合并即可
//3 2 4 8 1 7
//左右两边偏好序:2 3 4 1 7 8
//开辟一个新的空间，比较左侧第一个元素2和右侧第一个元素1的大小，
//小的放前面，大的放后面，继续往下比较，直到有一方越界，另一半的直接拷贝进来即可
//时间复杂度：O(N*logN)，空间复杂度O(N)
// 归并排序 数组左边的范围L==0，右边的范围R==length-1
func Process(arr []int, L, R int) []int {
if L == R {
return arr
}
mid := L + (R-L)>>1
//递归使得左边的元素有序
Process(arr, L, mid)
//递归使得右边的元素有序
Process(arr, mid+1, R)
//合并左边和右边的元素
merge(arr, L, mid, R)
return arr
}
//合并左右两边的元素
func merge(arr []int, L, m, R int) {
help := make([]int, R-L+1)
i := 0
p1 := L
p2 := m + 1
for p1 <= m && p2 <= R {
// 如果p1位置的值小于等于p2位置的值，将p1位置的值放入help
if arr[p1] <= arr[p2] {
help[i] = arr[p1]
p1++
} else {
// 如果p1位置的值大于p2位置的值，将p1位置的值放入help
help[i] = arr[p2]
p2++
}
i++
}
//如果p1没有越界，将剩余元素拷贝进help
for p1 <= m {
help[i] = arr[p1]
i++
p1++
}
// 如果p2没越界，将p2的元素拷贝到help里面去
for p2 <= R {
help[i] = arr[p2]
i++
p2++
}
// 将help的值赋给arr
for i := 0; i <= len(help)-1; i++ {
arr[L+i] = help[i]
}
}
8.5二分法查找有序数组是否存在某个元素 o(logn)
// 有序数组，必须先排好序
func binarySearch(arr []int, a int) (result int) {
if len(arr)==0{
return -1
}
//首先要排好序
end := len(arr) - 1
start := 0
index := int(0)
for start <= end {
index = (start + end)
if arr[index] < a {
start = index + 1
} else if arr[index] > a {
end = index - 1
} else {
result = index
return result
}
}
return -1
}
// 给定一个数组，数组左边的数小于给定的num,右边的数大于等于给定的num，要求空间复杂度O(1),时间复杂度O(n)
func HelanMethod(arr []int, num int) {
if len(arr) <= 1 {
return
}
min := -1
for i := 0; i < len(arr); i++ {
if arr[i] < num {
arr[min+1], arr[i] = arr[i], arr[min+1]
min++
}
}
fmt.Println(min)
}
//荷兰国旗问题 给定一个数组，数组左边的数小于给定的num,数组中间的数等于num，右边的数大于给定的num， 要求空间复杂度O(1),时间复杂度O(n)
func HelanMethod1(arr []int, num int) {
if len(arr) <= 1 {
return
}
min := -1
max := len(arr)
// for i := 0; i < len(arr); i++ {
// //小于 交换a[i]和小于界限的后一个元素，小于界限min往右移动，i++
// if arr[i] < num {
// arr[min+1], arr[i] = arr[i], arr[min+1]
// min++
// //大于 交换a[i]和大于界限的前一个元素，大于界限max往左移动,i不变，在判断交换后的元素和小于界限的元素关系的大小
// } else if arr[i] > num {
// //当max与i相等时停止
// if i == max {
// break
// }
// arr[i], arr[max-1] = arr[max-1], arr[i]
// max--
// //比较交换的值和最小区域值的大小关系
// if arr[i] < num {
// arr[min+1], arr[i] = arr[i], arr[min+1]
// min++
// }
// }
// //a[i]==num不动，i自增
// }
//当max与i相等时停止
for i := 0; i < max; {
//小于 交换a[i]和小于界限的后一个元素，小于界限min往右移动，i++
if arr[i] < num {
arr[min+1], arr[i] = arr[i], arr[min+1]
min++
i++
//大于 交换a[i]和大于界限的前一个元素，大于界限max往左移动,i不变，在判断交换后的元素和小于界限的元素关系的大小
} else if arr[i] > num {
arr[i], arr[max-1] = arr[max-1], arr[i]
max--
} else {
i++
//a[i]==num不动，i自增
}
}
}
8.6快速排序
借助荷兰国旗问题思想（小于 等于 大于），进行递归操作(该思想下时间复杂度O(n的平方))
快排1.0：时间复杂度O(n的平方)
快排2.0：时间复杂度O(n的平方)
快排3.0：时间复杂度O(nlogn) 随机选一个数做参考值，快排最好最坏情况变成了一个概率问题
//快速排序 arr[L....R]排好序
func quickSort(arr []int, L, R int) {
if L < R {
//等概率随机选一个数作为参照数，和数组最右边的数做交换，降低了时间复杂度
Swap(arr, L+rand.Intn(R-L+1), R)
p := Partiation(arr, L, R)
quickSort(arr, L, p[0]-1) //<区
quickSort(arr, p[1]+1, R) //>区
}
}
func Swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}
func Partiation(arr []int, L, R int) []int {
min := L - 1
max := R
for L < max {
if arr[L] < arr[R] {
arr[min+1], arr[L] = arr[L], arr[min+1]
min++
L++
//大于 交换a[i]和大于界限的前一个元素，大于界限max往左移动,i不变，在判断交换后的元素和小于界限的元素关系的大小
} else if arr[L] > arr[R] {
arr[L], arr[max-1] = arr[max-1], arr[L]
max--
} else {
L++
//a[i]==num不动，i自增
}
}
Swap(arr, max, R)
return []int{min + 1, max}
}
8.7堆排序 O(nlogn)
大顶堆和小顶堆.png
//大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
//小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
func heapSort(arr []int) []int {
arrLen := len(arr)
buildMaxHeap(arr, arrLen)
for i := arrLen - 1; i >= 0; i-- {
swap(arr, 0, i) //将堆顶元素与数组末尾的元素进行交换
arrLen -= 1
heapify(arr, 0, arrLen)//数组的前i分元素重新整理为大顶堆
}
return arr
}
//构建大顶堆
func buildMaxHeap(arr []int, arrLen int) {
for i := arrLen / 2; i >= 0; i-- {
heapify(arr, i, arrLen)
}
}
func heapify(arr []int, i, arrLen int) {
left := 2*i + 1
right := 2*i + 2
largest := i
if left < arrLen && arr[left] > arr[largest] {
largest = left
}
if right < arrLen && arr[right] > arr[largest] {
largest = right
}
if largest != i {
swap(arr, i, largest)
heapify(arr, largest, arrLen)
}
}
func swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}
100亿的两个大文件，求形同的url。精确查找和大致模糊匹配
1.分治法，将两个文件的url进行相同的hash运算，分成很多个小文件，hash值相同的文件进行url比较相同即可 （精确的匹配）
2.利用布隆过滤器思维，先计算第一个文件的hash值，将它存储，然后计算第二个的值，判断是否存在，存在即可能是相同的url（模糊的匹配）
一个整形数组，一种数出现奇数次，其他都是偶数次，找出这个数，时间复杂度o(n)，空间复杂度(1)
知识：异或 b^b=0,满足交互律
假设出现奇数次的数是a
arr:={a,a,a,b,b,c,c}
结果 aaabbcc=a
代码：
result:=0
for i:=0;i<len(arr);i++;{
result^=arr[i]
}
一个整形数组（均不等于0），两种数出现奇数次，其他都是偶数次，找出这两个数，时间复杂度o(n)，空间复杂度(1)
假设两个出现奇数次的数是a,b
数组所有数异或操作后,得到result:=a^b
取出一个数的最右侧的1，a&(~a+1)
与数组中的所有数做与运算，
result:=0
for i:=0;i<len(arr);i++;{
result^=arr[i]
}
rightOne:=result&(~result+1) //取出result最右侧的1
result1:=0
for i:=0;i<len(arr);i++;{
if arr(arr[i]&right==0){
result1^=arr[i]
}
fmt.Println(result1,result^result1)
}
则两个数是：result1 和result^result1
对数器，验证算法是否正确，随机生成测试数据，验证n次，不同算法实现相同功能，验证结果是否一样，可以验证算法是否正确
递归方法的使用步骤：
1.确定方法要做什么
2.找到递归结束的条件
3.找出函数的等价关系式
//斐波那契数列和青蛙跳台阶问题
//自顶向下递归
func method1(n int) int {
if n <= 2 {
return 1
}
// f(n)=f(n-1)+f(n-2)
return method1(n-1) + method1(n-2)
}
//自下向顶递推（减少重复计算的次数）
func method2(n int) int {
if n <= 2 {
return 1
}
sum := 0
f1 := 1
f2 := 1
for i := 3; i <= n; i++ {
sum = f1 + f2
f1 = f2
f2 = sum
}
return sum
}
// 阶乘 自下向上递推
func method3(n int) int {
if n <= 2 {
return n
}
sum := 1
for i := 1; i <= n; i++ {
sum *= i
}
return sum
}
// 阶乘 自顶向下
func method4(n int) int {
if n <= 2 {
return n
}
return method4(n-1) * n
}
求两个数R,L的中点：
常规写法（R+L)/2 R+L可能越界
L+(R-L)>>1 (R>L)，防止R+L越界，造成异常
master公式：递归时间复杂度
T(N)=aT(N/b)+O(N^d)
a递归次数
N/b子问题规模
O(N^d) 除去递归操作后的时间复杂度
各占情况总的时间复杂度计算公式：
master公式.png
归并排序时间复杂度符合log(b,a)=d=1故时间复杂度为NlogN
归并排序衍生出小和问题和逆序对问题算法题
排序算法的稳定性：值相同的元素排完序之后相对位置不会变，则是稳定的(基础数据类型没啥问题，对象的时候稳定性比较重要)
常见排序算法时间空间稳定性分析.png
稳定性和空间复杂度不能同时满足。
