题目(从1到n整数中1出现的次数—牛客网)

输入一个整数 n，求 1-n 这 n 个整数的十进制表示中 1 出现的次数。 例如，输入12，1-12 这些整数中包含 1 的数字有1、10、11 和 12，1 一共出现了 4 次。

算法思路

最简单的思路就是遍历所有整数，然后对每一个整数再遍历出每一个数位(通过 /、% 运算即可)，最后统计所有整数中含 1 的次数。但是此情况下的时间复杂度达到了 O(nlogn)，能不能降到 O(logn)？。

可以滴！！接下来，提出一个高效算法，它利用了数字的规律，挺不容易想到的。
既然时间复杂度这么低，那么就不可能去单独计算每个整数中 1 出现的次数了，所以就只能研究 1 出现的规律了。
由于我们可以计算出所有整数中 1 出现在每个数位(个位、十位、百位…)的总次数，因此最后 1 到 n 整数中 1 出现的次数=所有整数中含个位且其个位为 1 的总数 + 所有整数中含十位且其十位为 1 的总数+所有整数中含百位且其百位为 1 的总数
+…(项总数取决了 n 含的数位数,共 logn 项)。

下面以百位为例进行分析。 我们以百位 i(i=100) 将整数 n 分割为两部分。设a=n/i;b=n%i。

1. 如果 n 的百位上为 0，例如 n=31056，a=310,b=56。那么 1-31056 中百位含 1 的整数必然以 100-199 之间的数字作为后缀(共有100个)。而前缀的范围在 00-30 之间(不包括31的是因为31056中百位不是 1，忽略)，共31个，它等于a/10，因此此情况总的个数就是 a/10*i；
2. 如果 n 的百位上为 1，例如 n=31156，a=311,b=56。那么 1-31156 中百位含 1 的整数必然以 100-199 之间的数字作为后缀(共有100个)。而前缀的范围在 00-30 之间，共31个，但前缀为 31 时，百位含 1 的个数为 (b+1)个，即31100-31156 之间的数，因此此情况总的个数就是 a/10 *i+(b+1)；
3. 如果 n 的百位上数字大于等于2 ，例如 n=31256，a=312,b=56。那么 1-31256 中百位含 1 的整数必然以 100-199 之间的数字作为后缀(共有100个)。而前缀的范围在 00-31 之间，共32个,因此此情况总的个数就是 (a/10 +1) *i。

最后，将三种情况进行整合，得 (a+8)/10 *i，当百位大于等于 2 时，a多加了8就会进1，此时等价于情况 3 中的式子。最后利用 a%10判断整数 n 的百位是否为1，若为 1 ，则总次数还要多加上(b+1)。

算法实现

复杂度

由于算法只遍历了整数 n 的每个数位(共 logn 位)，所以算法的时间复杂度仅为 O(logn)。

参考

[1] <<剑指offer2>>
[2] 牛客网

题目(数组中连续子数组的最大和)

输入一个整数数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。例如输入的数组为 {1,-2,3,10,-4,7,2,-5}，最大的连续子数组为 {3,10,-4,7,2}，因此输出为该子数组的和 18。

算法思路

本题是经典的动态规划题目之一,所以我们利用动态规划的思路分析。首先以函数 f(i) 表示以第 i 个数字结尾的子数组的最大和，那么求解目标就是max(f(i))，(0<=i<=n)。那么如果以第 i-1 个数字结尾的子数组的和小于等于 0，那么我们所求的子数组只能从第 i 个数字开始了;如果以第 i-1 个数字结尾的子数组的和大于 0，那么我们再将第 i 个数字累积进去，得到新的子数组的和，最后只需要和已有最大值比较即可。据此很容易得到状态转移方程为：

算法实现

参考

[1] <<剑指offer2>>
[2] 牛客网

题目(数据流中的中位数—牛客网)

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用 Insert() 方法读取数据流，使用 GetMedian() 方法获取当前读取数据的中位数。

算法思路

本题解法有很多，比如如果数组无序，那么使用快速排序中的 Partition 函数可在 O(n) 时间内找到中位数，O(1)时间内插入无序数组;还可以每插入一个元素保持数组有序，那么插入元素需要 O(n) 的时间，而找到中位数只需要 O(1) 的时间(此情况同链表实现)；最后一种，也是下面的实现，即利用最大堆和最小堆，那么怎么操作呢？

首先我们定义一个计数变量 count，然后将第奇数个数插入最大堆，第偶数个数插入最小堆，这是为了保证两个堆的大小之差为 1。注意，插入并不是无条件的，当插入最大堆时，若待插入的元素比最小堆堆顶元素还大，那么先将其插入最小堆后取其新堆顶元素加入最大堆；同理，当插入最小堆时，若待插入的元素比最大堆堆顶元素还小，那么先将其插入最大堆后取其新堆顶元素加入最小堆。这样既保证了将数字平均分配到了两个堆中，也保证了最大堆中的数字都比最小堆中的数字小，以便快速找到中位数。那么此时，很容易得到中位数，如果输入了奇数个数，那么最大堆堆顶元素即中位数，否则中位数为两堆顶元素的平均值。

算法实现

复杂度

本算法实现的时间复杂度为：插入时间为 O(logn)，获取中位数的时间为 O(1)。空间复杂度为两个堆的大小。

参考

[1] <<剑指offer2>>
[2] 牛客网

题目(最小的k个数—牛客网)

输入 n 个整数，找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字，则最小的 4 个数字是 1,2,3,4,。

算法思路一

题目为最小的 k 个数，它是未知数，所以首先应该分类讨论 k 的各种特殊值。
如果 k<=0,或者大于数组大小，则无意义。另外，当 k 刚好就是数组长度时，输入数组即为所求。
对于输入数组的大小也该判断。

我们从求数组任意第 k 个大的数字的问题中得到启发，此问题的相似版本在上一篇文章，采用快速排序的基础思想partition 函数。它既是快速排序的基础，同时也可以用来查找 n 个数中第 k 大的数字。
我们利用快速排序中的分割算法找到那个在 k 位置上的划分点即可，因为划分算法会使得数组中的左半部分数小于划分位置上的数，后半部分的数大于划分位置上的数，那么此时我们的所求就是这左半部分数。(ps:此法会修改原数组，如不需要原数组可使用下述思路，他们适合于处理海量数据的，不需要一次性处理。)

算法思路二

我们利用最大堆来存储这个 k 个数。首先初始将数组前 k 个数送入堆中。然后将其余的数字都和堆顶元素(最大元素)比较,只要比堆顶元素小，我们就删除堆顶元素，将新的元素加入堆中，继续维护堆。最后，堆刚好就维护了最小的 k 个数。

另外为什么不用最小堆呢？因为如果用最小堆，那么我们需要将所有元素送入堆中，那么需要对 n 个元素调堆，而对每个元素的调整时间增加到了O(logn)，最后的总时间复杂度为 O(nlogn)。而使用最大堆进行求解，只需要要 O(nlogk)，关键就在于用于建堆的元素总数。

算法思路三

利用优先队列，其实思想和二类似，但是它比二代码上更简洁。优先队列默认优先值大的排在前面，其实是最大堆实现出来的。

算法实现一

算法实现二

算法实现三

时间复杂度

算法实现一，时间复杂度为O(n)，其余时间复杂度均为O(nlogk)。

参考

[1] <<剑指offer2>>
[2] 牛客网

前言

编写算法，不仅需要正确实现，还需要考虑到时间效率的问题。比如采用更好的解法，养成更好的编程习惯。说到编程习惯，其实如果采用 C/C++ 编程时，在进行传递复杂类型参数的时，需要采用引用(或指针)，而要避免使用值传递，因为从形参到实参会产生一次多余的复制操作。用 Java、C# 等做多次字符串的拼接操作时，也不要多次使用 String 的 + 运算符来拼接字符串，因为这样会产生很多 String 临时实例，造成时间和空间的浪费。更好的办法是用 StringBuild 的 Append 方法来完成字符串的拼接。

题目(数组中出现次数超过一半的数字—牛客网)

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。

算法思路一

本题最简单的做法是先排序再求解，但是时间效率最低需要 O(nlogn)，以下思路时间效率都只需要 O(n)。

根据数组的特点：数组中有一个数字出现的次数超过数组长度的一半，也就是它出现的次数比其他所有数字出现的次数之和还要多。那么我们采用采用阵地攻守的思想：第一个数字作为第一个士兵，守阵地，计数为 1。 如果遇到相同的数字，计数加 1，如果遇到不相同元素，即为敌人，同归于尽,计数减 1；当计数值为 0 时，表示没有士兵了，又以新的 i 值作为守阵地的士兵。最后一个留在阵地的士兵有可能就是主元素，即所求，所以只需验证即可，可再加一次循环，记录这个士兵的个数看是否大于数组一半即可。

算法思路二

根据数组的特点：数组中有一个数字出现的次数超过数组长度的一半，那么当数字有序的时候，所求的数字一定在有序数组的中位数上。假设中位数的索引为 k，那么现在问题就转为为求数组中第 k 大的数字了，而这个转换问题可利用快速排序的思想，在线性时间内得到解决。

算法实现一

算法实现二

参考

[1] <<剑指offer2>>
[2] 牛客网