算法笔记-数组/字符串

数组问题的时间复杂度优化

overalll

单纯的与数组相关的问题（包括字符串）， 题目本身通常不难， 难点在与如何优化时间复杂度。

例如：

• offer 39-41 ：
  • 找到数组中数量大于一半的数字
  • 找到数组中第k小的k个数
  • 找到流数据的中位数

这些问题， 使用单纯的暴力排序均可解答， 但时间复杂度较高。

可以使用的优化方法：

• Partition：

  • 如果问题问的是 第k个数怎么怎么样， 例如数组中第k大的数，或者最小的k个数， 那么可以使用Partition求解。

    因为通过快排的partition方法， 可以O(n) 的找到第k小的数字， 当然这也包扩小于第k小数字的所有数字。

• 二分：

  • 如果是找 两个数组中第k小的数字， 那么除了merge两个数组以外， 可以使用二分的思想， 当然使用二分的前提是两个数组均是排序的。

• 数据结构的利用：

  • priority queue： 最小堆， 最大堆
  • AVL Tree
  • 链表

  offer41以及offer40.