一、问题描述 假设数列 B={} 是由 n 个不重复的数字按从小到大有序排列得到的，有序数列 B 是未知的，仅方便后续分析描述，数列 A={} 由数列 B 随机重排列得到，现使用小顶堆算法求数列 A 的第 k 个最大的数，求算法的平均时间复杂度。 二、算法分析 算法总体分为两个阶段：“堆初始化”与“堆更新”，依次对两个阶段进行分析： 阶段1：选取数列 A 的前 k 个数字进行堆的初始化，设该堆的初始最小值为 ，可知 M 有 n-k+1 种可能，分别为 1、2、3 …… n-k+1，现计算每种可能出现的概率 P{M=m}： 易知从 n 个数字中随机选取 k 个数字，共有 种可能； 大于 的...

从数组中寻找周长最小的三角形，常规的思路是先排序，再从小到大依次搜索，再添加一些小优化就OK了。假设最短三角形的三条边依次是a、b、c（a<b<c），通过分析我们可以知道，b、c在排序后的数组中一定是相邻的，因为如果b、c中间还有数据（设为x），那么a、b、x会形成一个更短的三角形，与假设矛盾。如此，我们仅需将c设为遍历变量，便可以直接确定b，接下来只需要找到a就可以了，根据三角形性质，我们有a>c-b，借助二分查找法我们可以查找到0~b范围内比c-b大的最小值，这个值就是我们要的a。需要注意的是，从左到右按以上逻辑遍历数组查找到的第一组数据，不一定是最终结果（最优解），因为...

O(n)伤不起：模拟二进制运算，绝对不涉及乘法，复杂度为O(logN) 2进制乘法原理与10进制类似，但是2进制更加简单，因为2进制非0即1，所以乘数m的一个二进制位与被乘数n相乘的结果要么是0要么是n本身，只要在实际计算过程中根据m的某个进制位所在的位置对n进行移位就可以了。 当然，这里讨论的都是正数乘法，负数乘法涉及补码，可以转为正数后再运算，不过本题不涉及负数； 所以整个过程只涉及位操作（位与、位移）和加法运算。 在编写代码时，首先需要取得乘数m的某一个进制位:假设有变量 bitMask = 1，那么要取得 m 的第 k 位（从低位开始）二进制位的表达式就是： m & (b...

先占个位置，详细思路之后再写； 先贴个图片和源码上去： #include <iostream> using namespace std; int first_day_food(int day, int food) { if (day <= 0 || day > food) return 0; else { int times = 0, remain = food; if (day < 31) // 如果天数大于30天，那么食物绝对不会多（否则食物数量会超出int的上限） ...

一种优化思路：无须次次进行遍历 这道题目的大致思路其实都差不多，只不过看了许多答案，发现都是存储了所有字符，然后再进行遍历判断其实并不需要这样。 用户 txlstars 的回答和本文的优化相同（绝对不是面向 Ctrl+C 编程的～） 字符出现次数的判断（不重复字符）：这个做法大致相同，利用 Hash 思想采用128大小的计数数组进行计数也好，或者是使用 Map 键值对映射也好，都差不多，使用数组会更简单。 字符出现顺序的判断（第一个字符）：这里就是改进的关键之处了，容易发现，字符流中不重复的字符可能同时存在多个，我们只要把这些 “不重复字符” 保存起来就可以，而无需保存那些重复出现的字符，而为...

1. 最近几天牛客的《剑指Offer》编程练习貌似不能发题解博客了，或者说，题解可以发，但是不能在题目的题解区域显示出来，如图1、图2； 2. 一个长期存在的问题，牛客博客的浏览量可以通过刷新网页来增长，这明显不合理啊，不停按Ctrl + R，那浏览量不还得突破天际（这个截不了图）？？ 3. 编程通过排行榜把编译失败也算进去了，如图3、图4；

越界的简单解决方案：让符号位参与运算，并合理利用 INT_MAX/10 众所周知，这道题逻辑并不复杂，只是要判断结果是否出界却有点让人手忙脚乱，这里给出以下两种情景的解决方案（若有发现缺漏之处，望及时指出纠正！）： 能够处理最小负数：-2147483648 判断是否超出最小负数 ~ 最大正数的范围 一、关于最小负数：从true、false到 -1、1一般而言，我们习惯性地使用 bool 类型来表示数字是否为负数（标志位 isNegtive），并在计算过程中使用正数来表示中间结果，只有在最后一步才根据标志 isNegtive 将结果取负，这样一样，因为最大正数的绝对值小于最小负数绝对值，所以...

从到，比递归效率更高的方法：上限约束法 方法一：递归法 递归简单易懂容易实现，先来一次遍历以确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。现在让我们来分析一下递归方法的时间复杂度：二叉搜索树不一定是棵平衡二叉树，因此其树形可能长得奇形怪状，最坏的情况下可能退化成一类似链表的结构，此时我们需要遍历n趟，每趟都需要遍历剩余未确定的元素，因此，递归方法的最坏复杂度是 方法二：上限约束法 那么贪婪的我们不禁就会想，有没有更好的方法？？O(n)、甚至O(logn)？ 由于一个正确的遍历序列，我们可以在它任意一个位置故意篡改，因此势必要遍历所有的元素才能确定它的正确性，所以个人认为，这个问题的...

双栈法的优化：压缩还原 方法一：简单的双栈法在返回栈中的min值时，如果仅仅使用一个辅助变量min，则其值可能因为min元素被出栈而失效，常规的做法是额外添加一个同步栈（min栈），以保存记录之前所有的min值，相当于是使用了n个辅助变量，所以空间复杂度是O(n)。 但是，仅仅使用一两个辅助变量就真的不能达到目的了？？其实是可以的！我们考虑使用一种类似压缩的方法，来将数据栈和辅助栈合并成一个栈，因为经过分析可以发现，其实各个元素的值与最小值是有关联的，这之间存在着冗余的信息！ 一个初步的优化是将min栈中因为没有新的min值入栈而产生的重复的min值舍弃掉，这一做法可以参考一叶浮尘的博客，但是...

分享五种解题方法，仅为拓宽思路：（注：如果代码出现了段错误问题，可能是没有考虑到空数组，健壮性也是算法的一部分） 一、左下/右上元素移动法：十分简单巧妙，在看了徘徊的路人甲的题解才后知后觉；设M=min(m,n)，N=max(m,n)，复杂度为O(N)，详见链接题解：链接：https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e?f=discussion 二、双折半查找法：是我提交时使用的方法，没有法一简洁明了，但是也挺好用，复杂度最坏情况为O(M * logN)，不过总体上还是比较优秀的，大概率可以取...