有书共读：《剑指offer》第五章：优化时间和空间效率
5.1 面试官谈效率
问一些关于时间和空间效率的问题，这能够体现一个应聘者较好的编程素质和能力。
5.2 时间效率
只有对常见的数据结构和算法都了然于胸，才能在需要的时候选择合适的数据结构和算法来解决问题。
面试题39: 数组中出现次数超过一半的数字
先排序的算法时间复杂度为O(nlogn)
基于partition函数的时间复杂度为O(n)，即快速排序的方法
根据数组特点找出时间复杂度为O(n)，主要利用的是数组中有一个数字出现的次数超过数组长度的一半，即它出现的次数比其他所有数字出现的次数还要多，可以利用这个特性进行计数解决。
面试题40: 最小的k个数
先排序的方法的时间复杂度为O(nlogk)
利用快速排序的思想，我们可以在partition的时候操作求得最小的k个数字。
时间复杂度为O(nlogk)的算法，适合处理海量数据，即维护一个为k的容器，该容器用红黑树实现查找效率为O(logk)，现在我们把n个数***去，考虑容器满和不满的情况，就可以求得结果。
面试题41:数据流中的中位数
可以用partition函数找出数组中的中位数，在没有排序的数组中插入一个数字和找出中位数的时间复杂度为O(1)和O(n)
排序链表的方法可以在O(1)时间内得出中位数
用最大堆最小堆的方法可以实现插入O(logn)，查找O(1)的复杂度。
面试题42:连续子数组的最大和
这个需要找规律，子数组的开始元素总为正值，能够保证和最大。
另一个是用dp的方法
面试题43:1～n整数中1出现的次数
从数字规律着手能够明显提高时间效率
面试题44:数字序列中某一位的数字
找规律解决就能提高效率。
面试题45:把数组排成最小的数
按照字符串大小的规则急性排序就行了。
面试题46:把数字翻译成字符串
递归从左导游效率低，我们可以从右到左来计算。
面试题47:礼物的最大价值
动态规划的题目，dp[i][j]=max(dp[i-1][j],dp[i][j-1])+gift[i][j]
面试题48:最长不含重复字符的子字符串
动态规划的方法解决这个问题，需要分第i个字符之前已经出现过和未出现过两种情况，分别讨论这两种情况就可以。
5.3 时间效率与空间效率的平衡
面试题49:丑数
创建数组保存已经找到的丑数，用空间换时间，这个本人已经码过多次代码，所以就不做笔记了。
面试题50:第一个只出现一次的字符
用hash表就能够快速得到最优解。
面试题51:数组中的逆序对
归并排序的版本
面试题52: 两个链表的第一个公共节点
首先链表相交必然是Y字形，我们只需要找到两个链表的长度，求出长链表比短链表多几个节点，然后第二次遍历的时候就走这么多步，然后一起走就可以找到。
5.4 本章小结
降低时间复杂度
第一种是改用更加高效的算法；
第二种是用空间换取时间。
#笔记##读书笔记#
深信服二面238人在聊
查看1道真题和解析