数据结构与算法学习（一）：第一阶段知识总结

1. 复杂度概述

分类
1. 时间复杂度：全称渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系
  - 最好情况：在最理想情况下，算法执行所需的时间复杂度
  - 最坏情况：在最糟糕的情况下，算法执行所需的时间复杂度
  - 平均情况：找出所有的输入情况及相应的发生概率，然后再计算加权平均值（加权平均时间复杂度、期望时间复杂度）
  - 均摊
    - 个别情况下时间复杂度比较高的那次操作耗时，平摊到其他那些时间复杂度比较低的操作上
    - 能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度
    - 均摊时间复杂度就是一种特殊的平均时间复杂度
2. 空间复杂度：渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系
分析方法
1. 循环法则：只关注循环执行次数最多的那段代码
2. 加法法则：总复杂度等于量级最大那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

复杂度量级

量级	大 O 表示法	多项式量级
常量阶	O(1)	是
对数阶	O(logn)	是
线性阶	O(n)	是
线性对数阶	O(nlogn)	是
平方阶	O(n^k)	是
指数阶	O(2^n)	否（NP 问题）
阶乘阶	O(n!)	否（NP 问题）

时间复杂度为非多项式量级的算法问题叫做 NP 问题，即 Non-Deterministic Polynomial 非确定多项式

2. 数组概述

概念
1. 一种线性表数据结构（每个线性表上的数据最多只有前和后两个方向）
2. 用一组连续的内存空间，存储一组具有相同类型的数据（大小固定、内存连续、类型统一）
3. 支持随机访问，但插入、删除操作也因此比较低效（顺序移位，保证内存空间连续，需要注意可能导致 OOM）
操作
- 随机访问：支持随机访问，根据下标随机访问的时间复杂度是 O(1)；二分查找的时间复杂度是 O(logn)
  1. 一维寻址公式：a[k]_address = base_address + k * type_size（也是数组从 0 开始编号的原因之一，另外就是 C 语言的历史原因）
  2. 二维寻址公式：对于 m * n 的数组，a[i][j](i<m, j<n) 的地址为：a[i][j]_address = base_address + (i * n + j) * data_type_size
- 插入操作
  1. 在开头插入
    - 最坏情况时间复杂度是 O(n)：所有数据依次后移
    - 平均情况时间复杂度是 O(n)：每个位置插入的概率一样，所以 (1 + 2 + ... + n) / n = O(n)
    - 特定场景下，无序数组（数据没有任何规律），如果要将某个数据插入到第 k 个问题，为了避免大规模数据搬移，可以直接将第 k 位的数据数组元素的最后，再把新的元素直接放入第 k 个位置：时间复杂度为 O(1)
  2. 在中间第 k 位插入：平均情况时间复杂度为 O(n)；特定情况下，时间复杂度是 O(1)
  3. 在末尾插入：即最好情况时间复杂度是 O(1)
- 删除操作
  1. 在开头删除：即最坏情况时间复杂度是 O(n)
  2. 在中间第 k 位删除：平均情况时间复杂度是 O(n)
  3. 在末尾删除：即最好情况时间复杂度为 O(1)
  4. 实际上，在某些特殊场景下，不一定非要追求数组中数据的连续性，如果将多次删除操作集中在一起还行，删除的效率会提高很多。即，为了避免数组中待删除数据之后的数据元素被多次搬移，可以先记录下已经删除的数据，每次的删除操作并不是真正的搬移数据，只是记录数据已经被删除，当数组没有更多空间存储数据时，再出发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移次数（类似 JVM 标记清除垃圾回收算法的核心思想）
应用
1. 特别底层的开发，直接使用数组更合适。平时的业务开发，可直接使用编程语言提供的容器类，比如 Java 中的 ArrayList、C++ STL 中的 vector
2. 警惕数组的访问越界问题：数组越界在 C 语言中是一种未决行为，在 Java 中会抛出 java.lang.ArrayIndexOutOfBoundsException 异常
实现

3. 链表概述

概念
- 通过“指针”将一组零散的内存串联起来使用，插入、删除数据非常快速（需要注意可能导致频繁 GC）
操作
- 单链表
  - 查找：根据指针一个结点一个结点依次遍历，直到找到相应的结点，时间复杂度是 O(n)
  - 插入和删除：只考虑相邻结点的指针操作，时间复杂度是 O(1)（一般都是先查找然后再指针操作），Java 中实现类是 LinkedList（底层是用双向链表实现，效率更高）
- 循环链表
  - 概念：一种特殊的单链表，尾结点指针指向链表的头结点
  - 优点：从链尾到链头比较方便，更加适合处理具有环型结构特点的数据（比单链表实现要代码简洁很多），比如著名的约瑟夫问题（时间复杂度是 O(n*m)，其中 n 是总的个数，m 是数的数目）
- 双向链表
  - 概念
    1. 支持双向遍历，有一个后继指针 next 指向后面的结点，一个前驱指针 prev 指向前面的结点（以空间换时间）
    2. 查找、插入和删除的效率都比单链表高（因为双向链表中已经保存了前驱结点的指针），Java 中 LinkedHashMap 底层使用了双向链表
  - 操作
    - 删除结点中“值等于某个给定值”的结点：对于单链表和双向链表都需要从头结点依次遍历对比，直到找到值等于给定值的结点，通过指针操作将其删除，时间复杂度为 O(n) = 查找 O(n) + 删除 O(1)
    - 删除给定指针指向的结点：单链表需要从头结点开始遍历链表，直到 p->=q，p 是 q 的前驱结点，时间复杂度是 O(n)；双向链表因为保存了前驱结点的指针，时间复杂度是 O(1)
    - 对于一个有序链表：双向链表的按值查询效率也要比单链表高一些。因为可以记录上次查询的位置 p，每次查询时根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半数据
- 双向循环链表
链表代码 6 个编写技巧
1. 理解指针或引用的含义
2. 警惕指针丢失和内存泄漏
3. 利用哨兵简化实现难度
4. 重点留意边界条件处理
5. 举例画图，辅助思考
6. 多写多练，没有捷径
常见算法题

4. 栈概述

概念
1. 一种“操作受限”的线性表，只允许在一端插入和删除数据
2. 先进者后出，后进者先出（~~吃完就吐~~）
实现
1. 顺序栈：用数组实现
2. 链式栈：用链表实现
操作
- 入栈和出栈：时间复杂度是 O(1)，空间复杂度是 O(1)
支持动态扩容的栈
- 实现
  1. 底层依赖一个支持动态扩容的数组。当栈满了之后，就申请一个更大的数组，将原来的数据搬移到新数组中
  2. Java 中实现动态扩容数组的数据结构 ArrayList：Java 列表和队列（一）：剖析 ArrayList
- 入栈
  1. 空间够用，即最好情况时间复杂度是 O(1)
  2. 空间不够，最坏情况时间复杂度是 O(n)
  3. 均摊时间复杂度是 O(1)
- 出栈
  - 时间复杂度是 O(1)
应用
1. 函数调用栈：操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。注意，函数调用不一定非要用栈来保存临时变量，JVM 堆栈和数据结构堆栈不是一个概念
2. 表达式求值：编译器通过两个栈来实现表达式求值，其中一个是保存操作数的操作数栈，另一个保存运算符的运算符栈。从左向右遍历表达式，当遇到数字就直接压入操作数栈；当遇到运算符，就与运算符的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，就从运算符栈中取栈顶运算符、从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较
3. 括号匹配：用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，就从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配、“[”跟“]”匹配、“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能匹配的右括号或者栈中没有数据，则说明为非法格式
4. 实现浏览器的前进后退功能：使用两个栈 X 和 Y，把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当点击前进按钮时，依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了

5. 队列概述

概念
1. 一种操作受限的线性表数据结构
2. 先进者先出（~~吃完就拉~~）
实现
- 需要两个指针：①. head 指针，指向队头；②. tail 指针，指向队尾
分类
- 顺序队列
  1. 实现：用数组实现的顺序队列
  2. 时间复杂度：入队和出队操作时间复杂度都是 O(1)，出队时不用搬移数据，如果没有空闲空间只需要在入队时再集中触发一次数据的搬移操作
- 链式队列
  1. 实现：用链表实现的链式队列
- 循环队列
  1. 概念：把数组收尾相连，扳成一个环
  2. 实现：用数组实现的循环队列，确定好队空和队满的判定条件（队列为空： head == tail，队列已满：(tail + 1) % n = head）
  3. 缺点：队列满时，tail 指向的位置没有存储数据，所以循环队列会浪费一个数组的存储空间
- 阻塞队列
  1. 原理：在队列基础上增加了阻塞操作。在队列为空的时候，从队头取数据会被阻塞；如果队列已满，则插入数据的操作会被阻塞
  2. 实现：
  3. 算法：使用阻塞队列实现生产者/消费者模型
  4. Java 提供的专门的阻塞队列实现
    - 接口：BlockQueue 和 BlockingDeque
    - 基于数组的实现类：ArrayBlockingQueue
    - 基于链表的实现类：LinkedBlockingQueue 和 LinkedBlockingDeque
    - 基于堆的实现类：PriorityBlockingQueue
- 并发队列
  1. 概念：线程安全的队列
  2. 实现：
    - 方式一：直接在 enqueue()、dequeue() 上加锁，锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作
    - 方式二：基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列，所以循环队列比链式队列应用更加广泛
应用
1. 平时的业务开发很少直接用到队列，一些具有特殊性的队列应用比较广泛，比如循环队列、阻塞队列和并发队列
2. 队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过队列这种数据结构来实现请求队列
3. 高性能队列 Disruptor、Linux 环型缓存，都用到了循环并发队列（Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等）

6. 递归概述

什么样的问题可以用递归来解决
1. 一个问题的解可以分解为几个子问题的解
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 去的过程叫“递”，回来的过程叫“归”，存在递归终止条件
递归代码编写技巧
1. 找到如何将大问题分解为小问题的规律，基于此写出递推公式，推敲终止条件，再将递推公式和终止条件翻译成代码
2. 只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤
3. 分治是一种解决问题的处理思想，递归时一种编程技巧
递归代码编写难点
1. 警惕堆栈溢出
  - 系统栈或者虚拟机栈空间一般都不大，如果递归求解的数据规模很大调用层次很深一直压入栈，就有堆栈溢出的风险
  - 可以通过在代码中限制递归调用的最大深度，但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用
2. 警惕重复计算
  - 可以通过一个数据结构比如散列表来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算
3. 复杂度方面
  - 在时间复杂度上，递归代码里多了很多函数调用，当这些函数调用的数量比较大时，就会积聚成一个可观的时间成本
  - 在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销
4. IDE 调试递归代码方法：打印日志发现递归值，结合条件断点进行调试

常见算法题

青蛙跳台阶

// 和斐波那契数列的区别在于起始数字不同，最佳解法是动态规划
class Solution {
    private int[] memo;

    public int numWays(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return jump(n);
    }

    private int jump(int n) {
        if (memo[n] != -1) {
            return memo[n];
        }
        if (n == 1 || n == 0) {
            return 1;
        }
        memo[n] = (jump(n - 1) + jump(n - 2)) % 1000_000_007;
        return memo[n];
    }
}

汉诺塔问题

class Solution {
    /**
     * 将 A 上的所有盘子，借助 B，移动到C 上
     * @param A 原柱子
     * @param B 辅助柱子
     * @param C 目标柱子
     */
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        movePlate(A.size(), A, B, C);
    }

    private void movePlate(int num, List<Integer> original, List<Integer> auxiliary, List<Integer> target) {
        if (num == 1) {    // 只剩一个盘子时，直接移动即可
            target.add(original.remove(original.size() - 1));
            return;
        }

        movePlate(num - 1, original, target, auxiliary);   // 将 size-1 个盘子，从 original 移动到 auxiliary
        target.add(original.remove(original.size() - 1));   // 将 第size个盘子，从 original 移动到 target
        movePlate(num - 1, auxiliary, original, target);   // 将 size-1 个盘子，从 auxiliary 移动到 target
    }
}

斐波那契数列

普通递归：包含大量重复子问题，时间复杂度高；递归调用栈太深时，空间复杂度高，容易导致栈溢出

public class Fibonacci {
	public static long fibonacci(int index) {
		if(index <= 1) {
			return index;
		} else {
			return fibonacci(index - 1) + fibonacci(index - 2);
		}
	}
}

尾递归优化：即 returen 语句不包含表达式。不会有重复计算，具有线性迭代特性，栈不会增长、不会导致栈溢出

public class Fibonacci {
	public static long fibonacciTailRecursion(long index) {
		return fibonacciTailRecursion(index, 0, 1);
	}
	public static long fibonacciTailRecursion(long index, int curr, int next) {
		if(index == 0) {
			return curr;
		} else {
			return fibonacciTailRecursion(index - 1, next, curr + next);
		}
	}
}

动态规划

public int fib(int n) {
        if (n <= 1) return n;
        int[] f = new int[n+1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i < f.length; i++) {
            f[i] = -1;
        }
        return fib(n, f);
    }

    public int fib(int n, int[] f) {
        if (n <= 1) return f[n];
        if (f[n] != -1) {
            return f[n];
        } else {
            f[n] = (fib(n-1,f) + fib(n-2, f)) % 1000000007;
        }
        return f[n];
    }

平衡二叉树

方法一：自顶向下的递归

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

时间复杂度：O(n^2)，其中 n 是二叉树中的结点个数。最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有结点，时间复杂度是 O(n)。对于节点 p，如果它的高度是 d，则 height(p) 最多会被调用 d 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 h 满足 O(h)=O(logn)，因为 d≤h，所以总时间复杂度为 O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2)
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n

方法二：自底向上的递归

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n

二叉树的最大深度

方法一：深度优先搜索

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次
空间复杂度：O(h)，其中 h 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度

方法二：广度优先搜索

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }
}

时间复杂度：O(n)，其中 n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次
空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)

递增顺序查找树

方法一：中序遍历 + 构造新的树

class Solution {    
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> vals = new ArrayList();
        inorder(root, vals);
        TreeNode ans = new TreeNode(0), cur = ans;
        for (int v: vals) {
            cur.right = new TreeNode(v);
            cur = cur.right;
        }
        return ans.right;
    }

    public void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}

时间复杂度：O(n)，其中 n 是树上的节点个数
空间复杂度：O(n)

方法二：中序遍历 + 更改树的连接方式

class Solution {
    TreeNode cur;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode ans = new TreeNode(0);
        cur = ans;
        inorder(root);
        return ans.right;
    }

    public void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        node.left = null;
        cur.right = node;
        cur = node;
        inorder(node.right);
    }
}

时间复杂度：O(n)，其中 n 是树上的节点个数
空间复杂度：O(n)

给单链表加一

class Solution {
  public ListNode plusOne(ListNode head) {
    // sentinel head
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;
    ListNode notNine = sentinel;

    // find the rightmost not-nine digit
    while (head != null) {
      if (head.val != 9) notNine = head;
      head = head.next;
    }
    
    // increase this rightmost not-nine digit by 1
    notNine.val++;
    notNine = notNine.next;
    
    // set all the following nines to zeros
    while (notNine != null) {
      notNine.val = 0;
      notNine = notNine.next;
    }
    
    return sentinel.val != 0 ? sentinel : sentinel.next;
  }
}

时间复杂度：O(n)，最多只需遍历两遍链表
空间复杂度：O(1)

两两交换链表中的结点

方法一：递归

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作
空间复杂度：O(n)，其中 n 是链表的节点数量。空间复杂度主要取决于递归调用的栈空间

方法二：迭代

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}

时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作
空间复杂度：O(1)

7. 排序算法概述

排序算法	执行效率	内存消耗	稳定性	是否基于比较	应用场景
	1. 最好情况、最坏情况、平均情况时间复杂度 2. 时间复杂度的系数、常数、低阶 3. 比较次数和交换（或移动）次数	1. 排序算法的空间复杂度，需要通过原地排序来分析 2. 原地排序算法特指空间复杂度是 O(1) 的排序算法	稳定排序算法可以保持数据相同的两个对象，在排序之后的前后顺序不变
冒泡排序	1. 有序：最好 O(n) 2. 倒序：最坏 O(n^2) 3. 平均 O(n^2)	原地排序	稳定	是	适合小规模数据
插入排序	1. 有序：最好 O(n) 2. 倒序：最坏 O(n^2) 3. 平均 O(n^2)	原地排序	稳定	是	适合小规模数据
选择排序	1. 最好、最坏和平均都是 O(n^2)	原地排序	不稳定	是	适合小规模数据
归并排序	1. 最好、最坏和平均都是 O(nlogn)	空间复杂度是 O(n)	稳定	是	适合大规模数据
快速排序	1. 最坏 O(n^2) 2. 平均 O(nlogn)	原地排序	不稳定	是	适合大规模数据

8. 三种线性排序（复杂度为 O(n)）

排序算法	概念	应用	是否基于比较	举例
桶排序	1. 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序 2. 桶内排外序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了	1. 适合用在外部排序中 2. 要排序的数据需要很容易就能划分成 m 个桶，并且桶与桶之间有着天然的大小顺序 3. 数据再各个桶之间的分布是比较均匀的	否	根据年龄给 100 万用户排序/按订单金额给 10GB 的订单数据排序
计数排序	1. 桶排序的一种特殊情况 2. 当要排序的 n 个数据所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶	1. 只能用在数据范围不大的场景中 2. 只能给非负整数排序	否	给 50 万考生按成绩排名
基数排序	1. 对要排序的数据有要求，需要可以分割出独立的“位”来比较 2. 位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的地位就不用比较了 3. 每一位的数据范围不能太大，可以用线性排序算法来排序，否则时间复杂度无法做到 O(n)		是	给 10 万个手机号码排序

9. 二分查找概述

概念
1. 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想，时间复杂度是 O(logn)
2. 每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0
3. 适合处理静态数据，也就是没有频繁的数据插入、删除操作
编写代码要点
1. 关注循环退出条件
2. 关注 mid 的取值
3. 关注 low 和 high 的更新
应用
1. 二分查找只能用在数据是通过顺序表来存储的数据结构上
2. 二分查找针对的是有序数据，如果数据时无序的，需要先排序
3. 数据量太小不不适合二分查找，直接用顺序遍历即可
4. 数据量太大不能用二分查找

4 个常见变形问题

查找第一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

查找最后一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

查找第一个大于等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

查找最后一个小于等于给定值的元素

public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

变形问题出错要点
1. 终止条件
2. 区间上下界更新方法
3. 返回值选择

常见算法题

二分查找

class Solution {
  public int search(int[] nums, int target) {
    int pivot, left = 0, right = nums.length - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (nums[pivot] == target) return pivot;
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
    return -1;
  }
}

时间复杂度：O(logn)
空间复杂度：O(1)

x 的平方根

方法一：袖珍计算器算法

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
}

时间复杂度：O(1)，由于内置的 exp 函数与 log 函数一般都很快，我们在这里将其复杂度视为 O(1)
空间复杂度：O(1)

方法二：二分查找

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

时间复杂度：O(logx)，即为二分查找需要的次数
空间复杂度：O(1)

方法三：牛顿迭代

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}

时间复杂度：O(logx)，此方法是二次收敛的，相较于二分查找更快
空间复杂度：O(1)