Leetcode按题目类型总结(三)

二分搜索

Posted by Jingming on October 15, 2017

所有代码详见:https://github.com/jingminglake/Leetcode

总体思路

二分搜索思想:搜索的内容是未知的,但是,首先知道解空间的是一段连续的上升或者下降空间,有其明确下限和上限(例如整数就有最大值、数组下标其实也存在最大值、或者有序矩阵中最右下角的值就是最大值),同时有条件公式来 知道要搜索的内容是大了还是小了,这样就能缩减答案范围,直到范围很小,变成一个点。

搜索的题目的特点是:在序列(排序或未排序)找到符合某种特点的元素。如果是精确查找,那么二分搜索在等于时候就应该返回,如果是查找符合条件的第一个,那么等于时候不能返回,而是要缩减搜索范围。

基于index的二分搜索题目

基于index的二分搜索边界条件极容易出错,来看: mid = left + (right - left) / 2,并使用 left < right做判断。 例如:left = 0,right = 1。mid = 0。 如果此时让left = mid,有可能会死循环,因为left没有变化,下次计算出的mid和之前一样。 使用left = mid + 1,有可能在最终使用left返回的时候,left实际上跳过了结果。 此时让right = mid,就说明right最少默认的减了1,没毛病。 使用right = mid - 1,有可能在最终使用right返回的时候,right可能跳过了结果。

因此,可以得出:如果使用left < right,那么必须使用left = mid + 1,避免死循环以及结合right = mid,防止跳过答案,但是要防止left做结果的情况。

同理,如果使用left <= right做判断。必须使用right = mid - 1来避免,因为left可能等于right,这样mid永远等于left和right,会死循环。

改进方法: 使用left + 1 < right做判断。 这样竟然就可以使用left = mid,这是因为left永远是比right要小2的,所以每次算出来mid都会比left大1。

另外,left + 1 < right相比于left < right。最终的left和right必然指向不同的两个相邻index,后者最后left和right指向同一个元素。

left + 1 < right也存在自身缺点:

如果一开始只有两个元素,且left、right一开始指向的元素就不合法,那么就不能明确的知道left指向的是答案,还是right指向的是答案了。不同于使用left <= right就可以避免一开始left和right有可能不合法的问题。

二分搜索的测试用例:(1) 是否输入有序 (2)target在输入的两侧(3)target在输入的中间(4)输入的元素只有一个(是target或者不是target)(5)输入的元素有两个(包含target、不包含target)(6)输入元素有多个(6)上面几种的组合。

lower_bound: x >= t中最小的x,所谓最小也就是从小到大排序中最靠近左侧的; upper_bound: x > t中最小的x。如果不存在x > t,那么返回最后一个下标。 例如:10 10 10 20 20 20 30 30; 20的lower_bound是第一个20,upper_bound是30。

总结:综上所述,二分搜索的模板多,且边界条件很难考虑。因此,在解所有的二分搜索我都使用尽量使用一种万能模板: mid = left + (right - left) / 2; left = mid; // left每次必然移动一位 right = mid; // right每次必然移动一位 left + 1 < right;// left必然和right隔2个index,且结果必剩下两个元素

这样,结果是剩下的两个元素之一。另外,此模板一开始的时候,必须指向两个不同的元素。

基于值的二分搜索

需要敏锐的找出值本身的上限和下限。例如378题,矩阵的左上角是最小值,右下角是最大值。

然后取出值的中间值M,对原本数据结构进行范围缩减。378题中,首先对矩阵找出小于等于M的元素的数量, 怎么找呢?其实就是240题的变种,240题是search一个具体数,其实对任何一个未知数,都可以search它的upper_bound。 如果搜索到的数量是小于k的,那么M不够大;反之,M太大;最后,如果M缩减到一个点的时候(注意不存在提前返回),就可以说,M就是答案。

基于数据结构的二分搜索

例如优先级队列,它本身的出队列就是O(logN)的时间复杂度,虽不是二分搜索,但是可以解类似二分搜索的题目。

例如二分搜索树,本身自带的查数据就是二分搜索,也需要掌握手动搜索二分搜索树上一个特定节点(例如lower_bound, upper_bound)的能力。

具体题目

278.First Bad Version

题意:左侧为好版本右侧为坏版本,求第一个坏版本。

:此题使用left + 1 < right模板。保证一开始left和right指向不同元素。答案在最后剩余的两个元素中,

其中left永远指向好版本的下一个,在最后两个元素时候,left可能为好,也可能为坏。

同理,right永远指向坏版本的前一个,在最后两个元素时候,right可能为好,也可能为坏。

但是,输入的结构是合法正确的情况下,最终结果一定是在left或者right。

744.Find Smallest Letter Greater Than Target

题意:也就是求lower_bound。

:此题是278的变种,继续用使用left + 1 < right模板。

区别在于,left和right都不比target大的时候,意味着所有元素都比target小,因此第一个字母作为结果返回。

34.Search for a Range

题意:搜索一个数的第一次出现位置和最后一次出现位置。一个数组中有不止一个的target,现在要找出最左边target和最右边的下标,数组中target只存在一个时候,答案里面的两个下标要相等。

: 继续使用left+1 < right模板做两次二分搜索得出两个位置,两次二分搜索的区别是,在等于target时候,第一次搜索要收缩right,第二次搜索要收缩left。

PS. 使用其他方法也可以,但是边界条件非常容易出错。

74.Search a 2D Matrix

题意:在mxn矩阵中找target,矩阵的特点是,从左到右升序,且每一列的第一个数大于上一列的最后一个数。

:注意此题每一列的第一个数大于上一列的最后一个数,所以实际上,就是一个从左到右,从上到下的一维升序数组,

所以可以继续使用之前的二分搜索模板,但是注意要把一维坐标转到二维坐标以便找到对应的数。

转化方法: 二维坐标(0, 0) 到(m - 1, n - 1)转成一维坐标(0,mn - 1),转化方法是m * x + y = z; x = z / m, y = z % m。

解法时间复杂度是O(logmn),空间复杂度为O(1)。

另外也可以使用两次二分搜索,先找到行,在从行找到列,但是代码写起来重复性高。

PS.与240题区别:240解法虽适用于74题,但240解法时间复杂度是O(m + n),不够快。

240. Search a 2D Matrix II

题意:此题和74题区别在于,不是每下一行都是严格大于上一行的,但是列还是递增的。

:此题解法如果使用二分搜索,那么时间复杂度是O(m logn)。

但是此题有更快解法: 关键就在于矩阵的自身特点。从矩阵右上角元素向左看递减,向下看递增。

这样保持两个指针,分别表示行和列,开始指向右上角的那个元素。如果该元素比target大,那么说明当前行不可能存在解,因此行指针加1,表示去掉第一行,如果该元素比target小,说明最后一列不存在解,因此列指针减1,表示去掉最后一列。

最终,只要行或列指针越界,那么就说明找不到,反之,就一定能最终指向和target相等的元素。因为每循环一次,行或列都变化1,所以时间复杂度是O(m+n)。

378. Nth Smallest Element in a Sorted Matrix

题意:nxn矩阵,每行是有序的,每列是有序的,都是增序。求矩阵中第k大的数。

:首先理解第K大的数,第K大的数是可能和第K-1大的数一样大的,例如序列全为1,那么

方法一:暴力解,对整个矩阵使用quickselect,时间复杂度是O(n^2)。此方法并没有使用有序的性质,因此不是最优解。

方法二:使用优先级队列,因为每行是有序的,那么我们可以做merge k个list来解,也就是将第一列所有元素进入优先级队列(最小队列),然后每次将最小值出栈,把出栈元素对应行下一个元素放入队列,这样进行k-1次操作后,堆顶就是答案。此方法时间复杂度是O(klogn),其中k的范围是0到n^2,也就是说,最坏情况下, 时间复杂度是O(n^2 * logn)。

方法三:使用对值的二分搜索。 首先找到值上下界,也就是矩阵的左上角和右下角分别是最小值和最大值。 然后,每次对中值M,查看矩阵中有多少个元素小于等于它(240的变种方法,关键是只花费n时间),最后,M缩减到一个值(是缩减到最小,不存在提前返回)的时候,矩阵中恰有k个元素小与等于它,那么就是答案。 理解:满足kth(矩阵中恰有k个元素小与等于)的值有很多个,但是只要其中最小的,因为最小的必然等于矩阵中的一个值,刚好满足题目需要。 还有一种情况,[[1,2],[1,3]],1的时候,最小值1也至少比两个数要大,此时返回1即可。

时间复杂度为O(n * logX),X表示矩阵中的最大值减去最小值。

推荐方法二,三。

153.Find Minimum In Rotated Sorted Array

题意:有序数组旋转后,求里面最小数,注意所有数字不重复。

:不重复的数字很关键。这样Rotated Sorted Array的特点是:最左边比最右边小的时候,Rotated Sorted Array相当于没有旋转,而只要发生了非0的真正旋转,那么最左边一定比最右边大。

在数组发生真正旋转情况下,二分搜索,如果mid指向的数比0处的数大,我们知道在左半边,否则在右边半。

154.Find Minimum In Rotated Sorted ArrayII

题意:此题与153题的区别是,含有重复的数字。

:首先不能通过最左边等于最右边来知道是否旋转过。小于则没有旋转,大于一定旋转过。

解决此题的一个技巧是,通过只比较mid和right来判断mid在左侧还是右侧,和right比较的时候,是可以屏蔽掉数组是否已经被旋转这个问题,

因为mid比right大,就说明落入左侧,而左侧就是未旋转这个问题。

mid比right小,那么mid一定落在右侧,也就是此时一定是一种旋转过的结构。

如果mid等于right:考虑这个例子[3,3,3,1,3]、[10,1,10,10,10],无法判断答案是在左半边还是右半边。

因此,此时采用right–来缩减答案的范围。 为什么不能使用left++呢? 来看[10,1,10,10,10],left++会跳过正确答案(一开始10等于10,left指向1,然后还是10等于10,left跳过答案),

实际上,这是由于本题的数据结构决定的,来看[3,3,3,1,3],拆分成左右就是[3,3,3]和[1,3];而[3,1,3,3,3],拆分成左右的时候

注意是[3]和[1,3,3,3],而不是[3,1]和[3,3,3]!也就是说,并不是对称的,说白了,左侧可能只有一个元素,而右侧始终有一个以上的元素,

如果左侧只剩一个,如果left++会有跳过的风险(跳过意味着破坏了”旋转过”的这种结构,也就是left突然变小导致只有右侧没有左侧,因此在一开始考虑mid落入左侧还是右侧已经失去意义),而right–则不会。

33.Search in Rotated Sorted Array

题意:已经排序好的数组进行旋转后,在里面搜索。

:方法一:先使用153解法找到最小元素的下标,然后使用正常的二分搜索,只不过下标要进行偏移运算。

方法二:首先画出数组两种可能的图,一张是没有旋转的,就是递增的,一张是前半部分递增,后半部分也递增,但是比前半部分都小。 经过观察,就发现,如果是0比size - 1处小,那么属于第二种情况,否则属于第一种情况。 但是二分查找过程并不是这样分的,这样分太细了,代码很长。

关键在于, 先区分mid是在前半段,还是后半段,前后半段内部是连续变化的。

如果mid在前半段,那么看target是否在left和mid之间(要看left,因为target可能在后半段),如果是,则right=mid来缩减范围,如果不是,left=mid来缩减范围;

如果落在后半段,那么看target是否在mid和right之间,如果在,则left=mid,如果不是right=mid。 nums[mid] == target就返回。 此题继续使用到left + 1 < right的模板。

如何判断mid在前半段还是后半段?看num[mid]是否比num[right]大(为什么不考虑num[left]? 因为比num[right]大可以区分旋转非旋转两种情况),nums[mid]等于target时候直接返回mid。

这么设计的理解:通用解法,把未旋转当作是旋转的特例来看,也就是说,把未旋转当作mid落入左半边的情况来看。

PS.使用left + 1 < right技巧要判断数组为空的情况,直接返回。

81.Search in Rotated Sorted ArrayII

题意:此题与33题的区别是,含有重复的数字。

:同样的,在nums[mid]等于nums[right]的时候,不能轻易的判断mid是在前半段还是在后半段,所以让right–来缩减答案的范围。 此题使用left++仍然不行,理由是:此题解法是需要维持通用的,也就是默认左半边是一定递增的,右半边有没有元素都无所谓,使用left++无疑存在有破坏左侧递增的风险, 而right–不会破坏这一性质。

50.Pow(x, n)

题意:求指数。

:此题关键在于用二分来减少乘法运算次数,

方法一:要算x的100次方,只需要先算x的50次方的结果sub,然后在需要sub * sub即可得到x的100次方。 奇数可以拆分,例如101,拆分为1 + 100, 在解决100之后,那么在乘以x一次。

方法二:x的100次方,缩减为x平方的50次方,继续缩减到次方为0。

递归出口:x的0次方等于1。

边界条件,次方数为负数的时候,转为正数计算,x变为1/x。

162.Find Peak Element

题意:给出数组,找出其中任意一个peak值。可以假设nums[-1] = nums[n] = -∞。数组元素数量至少是1, 且nums[i] != nums[i + 1]。

:此题普通解法比较简单,在此记录logn的解法。

首先,明确数组中一定是有答案的,因为即使数组元素是单调递增或递减的,由于nums[-1] = nums[n] = -∞,那么第一个元素或最后一个元素就是peak。 其次,每个相邻元素是不等的,nums[i] != nums[i + 1],不然很难编码。

使用二分法,mid比mid-1和mid+1都大的时候就是peak,立即返回;

否则,如果是mid是处于递增趋势的,那么说明右侧一定存在答案;反之,如果是处于递减趋势的,那么左侧一定存在答案。

继续使用left + 1 < right的模板。

275.H-Index II

题意:求hIndex,引用数数组已经升序排好。hIndex的定义,有hIndex篇文章有hIndex及以上的引用数,剩下的文章每篇都不到hIndex的引用数。

: 此题是274题的变种。274题已经解释了此题的经典计算方法。不过,经典计算方法是需要降序排列的,此题是升序排列的。

因此可以先逆序,然后二分。但是逆序花费时间O(N),已经超过了二分的时间复杂度,因此不可取。

此题可以对hIndex和数组下标的映射进行补数的考虑,也就是说,把下标i处当作不在当作HIndex是i来考虑,而是当作N - i来考虑。具体如下:

假如作者发了100篇文章,那么hIndex是1到100,考虑下标为0的地方,也就是引用数最低的元素的地方,

如果引用数大于等于100,那么之后所有文章引用数是大于等于100的,那么hIndex就是数组长度100;

否则说明已经已经有一篇文章引用数是小于100的,也就是hIndex已经不可能是100了,最多99;

那么,看第二个元素,如果大于等于99,那么同理,hIndex是99,否则,看第三个元素,依次类推。总之,从左到右第一个大于等于len-index的,下标就是hIndex。

所以,可以知道,如果给定任意一个下标index,如果它的元素比的值 >= len - index,说明它可能是结果,如果它左侧的元素比len - index小的话,但是无论如何,结果一定在包括该元素的左侧; 否则,结果一定在不包含该元素的右侧。最左侧的 >= len - index的元素就是hIndex。也就是找到最后一个index,满足citations[index] >= len - index

继续使用left + 1 < right的模板,right始终指向已知的最左边的 >= len - index的元素,left始终指向已知 < len - index的最右边元素。 最后只剩两元素的时候,结果要么在left,要么是right,如果right也不符合条件,那么hIndex就是0。

PS. 如果是降序的,那么也是类似的分析,下标0处大于1,那么hIndex至少为1,下标1处大于2,那么hIndex至少为2,依次类推。

436.Find Right Interval

题意:给出一些无序的区间数组,要求对每个区间i寻找最近的右边区间j(startj >= endi且startj最小, 注意startj == endi算)在无序区间数组中的下标。

:取出start组成数组并排序,并利用map存下start对应真实数组下标。然后对每一个区间的end,在start数组中进行二分搜索,找到第一个不小于end的start,进一步取出真实下标。

410. Split Array Largest Sum

题意:给出一个正数数组,和一个数字m。现在求将数组分割成m个部分(要求是连续片段),要求是切割后所有小区间之中区间和最大值最小。

:方法一:使用对值的二分搜索法。首先,如果m和数组元素个数相等,那么返回元素最大值L就行了,否则,如果m=1,那么返回所有值的总和S。那么我们知道,答案一定介于L和S之间。这样我们可以使用值的二分搜索。 对于mid值,我们按mid值进行分组,如果可以分成小于等于m组,说明mid偏大;反之,如果分为大于m组,说明mid值偏小。这样最终找到一个可分成m组情况中最小的mid。

如何根据mid分组:一句话,尽可能的分为最少组。具体来说,数组从前向后扫描,保证每一组连续元素最多的情况下且小于等于mid,

mid很大的情况下,组内很多元素,导致总分组数不足或等于m;反之,mid很小,导致结果大于m。

658. Find K Closest Elements

题意:给出一个已经排序好的数组,给出k,x两个整数,求数组中k个最接近x(x不一定是数组元素)的元素。返回的结果也需要是有序的。如果有正负距离x相等的元素,那么选择小的元素。

:已排序好的数组得出的结果必然是一个区间,而且该区间大小为k。 方法一:双指针。相当于去除n-k个不符合要求的元素。仔细分析,发现这些不需要的元素一定会从两头开始考虑。因此使用双指针,每次把两个指针指向的元素中距离x最大的那个删除,直到数组中只剩下k个元素,时间复杂度为O(N)。

方法二:二分搜索。关键在于理解此时搜索的并不是一个点,而是一个区间,但是由于区间长度是固定的,因此变成搜索区间的起点问题。 首先,起点的搜索范围是0到arr.length - k。 每次找到起点选择的下标mid后,看mid到mid + k - 1之间的区间(以mid为起点b和mid + k(右端点的下一个点)为终点e),区间和x的关系分为三种,一种是完全落在x的左边,一种是完全落在x的右边,还有一种是落在x上。 完全落在x的左边:e <= x,此时移动left; 完全落在x的右边:b >= x,此时移动right; 落在中间: 需要看哪个端点距离x更近,如果左端点更近(x - b < e - x),那么移动right,否则移动left。

洞见:找区间的核心是让x尽可能的处于区间的中心,或者更精确的说,k个元素和x的距离只和加起来最小。

继续使用left + 1 < right的模板。最终结果在left和right里,比较的时候,不需要比较两个数组和x的总距离,因为它们其实共享k-1个元素,只有一个元素不同, 只需要进行比较left和right + k - 1处与x的距离,就可以得出最终结果。

300. Longest Increasing Subsequence

题意:经典的最长子序列问题,子序列需要严格的递增(等于不行)。要求是使用nlogn的解法。

:经典解O(N^2):对每个点,需要考虑之前所有点,该点的值比当前值小,且该点的子问题结果长度最长。

但是此题要求nlogn。方法是使用额外的升序数据结构来二分搜索向前找的过程。

该数据结构为升序数组tail,tail数组的下标i所在元素,代表i+1长度的序列中结尾最小的值。该结构在每次扫描过程中O(1)时间动态更新,只需要更新第一个大于元素值的位置的元素。最终的结果就是tail数组的大小。

理解:对于序列0,8,4,12。当扫描到12的时候,tail数组为{0,4}。解释:以1为长度的序列是0,4或者8,其中0最小,选0;以2长度结尾的序列有(0,4),(0,8),选最小值4。 再举个例子,0,8,4,12,2,3。扫描到3的时候,以1为长度结尾的序列是0,8,4,12,2,我们选最小值0;以2为长度结尾的序列是(0,8),(0,4),(0,12),(0,2),我们选2;以2为长度结尾的序列是(0,8,12),(0,4,12),我们选12,所以tail数组的值为(0,2,12)。

所以,每次扫描一个元素的时候,先在tail数组中二分查找最后一个比该元素小或等于的元素,然后我们知道当前元素一定比tail数组中查找位置的下一个元素小(如果不存在,那么新增),而且该位置可以更新。最终的结果就是tail数组的大小。

参考:https://leetcode.com/problems/longest-increasing-subsequence/solution/

483. Smallest Good Base

题意:题目要求把一个十进制数n表示成以k(k >= 2)为底的全1的数。例如13可以表示为3进制的111,也即是3 ^ 2 + 3 ^ 1 + 3 ^ 0 = 13。现在要求找出满足条件的k中最小的那个。n的上下界是[3, 10^18]。

:先看基数为k的m位长度的全1串,他的大小可以根据等比数列公式计算,也就是(1 - k ^ m) / (1 - k) == n。其中有两个变量k和m,通过1000可以表示为基数为999的11串时候,我们发现,只要k= n-1,那么一定是有解11的,所以k的上界是n-1。但是n的上界实在太大。 再看m的上下界,m最小为1,m最大的时候,我们知道k == 2时候才能达到最大,所以n == (1 - 2 ^ m) / (1 - 2) == 2 ^ m - 1 ==> m <= log2(n + 1)。 所以一个解法就是,从大到小遍历每一个m,然后二分的搜索第一个满足条件的k。m从大到小保证了k是最小的。实际上,m确定之后,k的上界进一步缩小, 根据 n = 1 + k + k ^ 2 + … + k ^ m-1可以知道 n >= k ^ m-1 ==> k < n ^ (1/ (m-1) ) + 1。 所以,对于数3,它的选择就是看看能不能从0,2,12的这些最优结尾进行更新。我们看0,如果3接在0的后面,那么新长度为2,但是0,3并不比长度为2结尾的串有优势,所以不是合理选择。再看2,放在2的后面,可以使长度达到3,而且此时长度3的序列最后一个值是3,比12小,所以,12可以更新。再看12,12比3大,意味着新加入的3无法组成长度为3+1的新序列。所以选2,然后,把12更新为3。整体来看,总的效果等价于用二分搜索找到第一个比3大的,将3替换该值,新的tail数组是(0,2,3)。 所以,此方法tail数组就是对之前最优结果的高度压缩,只记录当前扫描数字为结尾的子串中长度为下标加1长度的序列的最合理的结尾。tail数组的维持是很自然的,不需要(0,8),(0,4),(0,12),(0,2)这种中间过程,它只需要每次找到合适的长度更新就可以。例如,找到不能更新12到长度4,但是能更新2,那么就知道该更新长度为3的结尾。

327. Count of Range Sum

题意:给出一个数组以及上下界,求出所有连续子数组的和在上下界之间的。

:此题暴力求解就是,先使用前缀和数组,然后两两看,计算所有的连续子序列,看值是否在上下界之间,时间复杂度是O(N^2)。 另一个解就是,先计算前缀和,然后利用multiset这个treemap,先存入0,然后每次存入当前前缀和元素,然后在set中查找之前能和他配合成为介于上下界的区间.

理解: lower <= preSum2 - preSum1 <= upper。其中preSum1已经在set里面了,然后将式子变形,我们知道 preSum2 - upper <= preSum1 <= preSum2 - lower。multiset求这个区间的方法就是lower_bound(找出第一个不小于给定值的数)求出preSum2 - upper元素所在的迭代器,然后upper_bound(找出第一个不大于给定值的数)求出preSum2 - lower元素所在的迭代器,然后相减(使用函数distance)就可以得出区间的长度。

此题如果使用Java语言,由于Java没有自带的去重的平衡BST,所以很难求解,因为自己手动写平衡BST是有难度的(因为数据本来就无序),使用JAVA的话,最好采用一种mergeSort的方法。

mergeSort方法的精髓在于,我们可以认为前缀和数组左半边和右半边都已经排好序了,剩下了的就是把左右半边进行合并操作。 但是除了合并,也需要这么考虑:右半边的下标是比左半边下标大的,也就是有资格减去左半边下标,得出一个区间和,而且由于是有序的,其实在发现大于upper的时候,其实有些类似于滑动窗口的跳过机制(我有质疑,网上解法并不是线性的,而是N^2的), 也就是线性时间内求出 n/2 * n/2 种下标组合的情况,当然,知道所有的组合情况是n(n-1)/2种(n个里面选2个),剩下的部分其实是变成了 n/4 * n/4 * 2 + n/8 * n/8 * 4 + ….,也就是1/4 + 1/8 + 1/16 + … = 1/2。这种覆盖率,和归并排序为什么可以最终保证排序是一个道理。

315. Count of Smaller Numbers After Self

题意:给出整数数组,然后求每个数字右边比它小的数的数量。

:方法一:暴力解。就是对于每个数扫描左边所有的数,时间复杂度是O(n^2),但是此题是hard,不会这么简单的,其时间复杂度至少应该是可以降到O(nlogn)甚至O(n)的。

方法二:二分搜索。 反过来扫描,把数存入到手写的平衡BST里面(有难度,实在不行BST不一定要平衡,但是时间复杂度不能保证是O(nlogn))。 另外一点,之所以要手写BST是因为其中结点要进行augment,augment的正是一个结点的rank。

方法三:mergeSort技巧。mergeSort技巧适合于任何基于两两比较的排序问题。mergeSort技巧的好处是能够将N^2次的比较减少到NlogN次的比较。

总的来说, mergeSort思路是这样:先把问题划分为左半边和右半边两个子问题以及将两个子问题合并得出最后结果的问题,也就是T(N) = T(N/2) + T(N/2) + X。

其中X是合并两个已经有序序列的成一个有序序列的问题,花费时间是N,而不是N^2,也就是说,比较的时候,并不是一个个的比较,而是由于有序,所以可以在发现不满足条件的时候,提前返回,将N^2次比较优化成N次比较。

这样就能把总体的时间复杂度将为O(NlogN)。

对于此题来说,在N^2次的比较的解空间内,仍然可以利用mergeSort的思路,也就是利用半边有序来减少比较次数,也就是需要在N的时间内解决X问题。

具体来说,对左半边的每个数,需要计算右半边的比其小的数的数量,总体花费N时间。

举个例子:左边为1,4,7,8;右边为3,6,7,9,11。一开始左右指针分别指向两边的开头,1和3比较的时候,发现,1比3小,此时意味着:

1比3之后的数都小,且3是右边第一个比1大的数,可以推出:右侧比1小的数数量为0。

此时1的结果计算完毕,左侧指针指向下一个要计算的元素4,右侧指针不动。

此时,发现4比3大,意味着:

3并不比当前要计算的元素4大,且此时要算计的元素是4,是所有尚未计算的元素中最小的元素,可以知道:此时右侧的3不能给之后过程做出贡献,所以

进行跳过,也就是说,此时右侧指针移动,左侧指针不动。

以此类推。。。

最后,如果左侧的元素还有剩余,意味着剩下的元素都比右侧任何元素大,此时继续遍历到最后,每个元素都加上右侧元素数量;反之,如果右侧元素有剩余,那么意味着左侧元素计算完毕,此时只需要考虑 排序的合并即可。

接下来就是计算左半边的元素在内部原序的时候,有多少元素比自己小,其实这是一个递归的子问题,递归到基本条件是,数组元素大小是1,也就是右侧没有比自己小的数。大于等于2的情况,都可以适用于之前的双指针解法。

另外,要注意的是,每次计算的元素,需要增加到它对应的原始数组的位置上。发现,如果要构建值到下标的映射会不方便,因为元素值存在重复。这里有一个技巧是: 排序的时候,不把元素放到该位置,而是把元素的下标放到该位置。也就是说,既然我们找不到值到下标的映射,那么干脆我们只记录下标好了,有了下标,就能找到值。 建立indexes数组,一开始其中的下标对应到原始数组的下标。

推荐方法三。归并排序的模板一定要掌握,一个简洁的归并的模板参考:https://github.com/jingminglake/MyDataStructures/tree/master/mergeSort。

其中merge的思路是:先使用额外空间记录规定后的结果,然后,根据偏移量,把该额外空间修改回之前的数组对应的位置。

参考:http://www.micili.cn/算法与数据结构/2017-02-18.html?t=1527304772

475. Heaters

题意:给出房子坐标数组和加热器坐标数组,求加热器最小半径多少可以让每个房子供暖。

:此题关键是加热器坐标不一定一定在某个房子坐标上。所以就要找出所有房子距离自己最近的加热器有多远,其中最大的就作为结果返回。 其中,搜索距离自己最近的加热器可以使用二分搜索,先对加热器数组排序,然后让房子坐标一个个进行二分查找,使用找出距离房子最近的加热器的距离。

540. Single Element in a Sorted Array

题意:一个排序好的正数数组里面,只有一个元素是出现一次的,其他的出现两次,现在要求出只出现一次的元素。

:由于是排序好的,而且里面蕴含规律,所以应该是使用二分搜索来解的。 难点在于:如何根据mid的特点来把问题变为一半。首先,mid如果和自己的左右都不等,那么他就是唯一的那个元素;然后剩余情况下,左边元素和右边元素必有一个是与自己相等的,那么如何知道答案在左边还是右边呢? 其实取决于被mid隔开的两个相等部分(因为元素总数必然是奇数,所以按中点切割后剩余两部分相等)长度是奇数还是偶数,例如是偶数,那么一旦是左边元素和自己相等,这意味着排除掉左边元素和mid自己后,那么左边剩余的是奇数个元素,也就意味着答案必然在左侧;反之如果和右边元素相等,那么答案在右侧。长度是奇数的情况同理分析。

此题不能使用left+1<right的模板。需要使用left < right的模板,这一点可以通过分析base case了解。 此题需要分奇偶考虑,还是挺难的。

528. Random Pick with Weight

题意:给一个整数数组,数组里面元素正整数代表了权值,现在要求根据权值大小的概率来生成数组对应的下标。

:首先可以知道每个下标对应的概率,但是发现不能直接根据概率来生成下标,例如,使用3/5的概率来生成了一个数,说明不了任何问题。真正的思路就是,概率是一个[0, 1]的区间,区间内会根据权值切分成不同的区间, 这样,生成一个区间内的数,这个数落入了哪个区间,那么就是生成了哪个下标。 首先,需要构造这样的区间;其次,要根据生成的数找到相应的区间。

构造区间:例如{1,2,3},那么概率是{1/6, 2/6, 3/6},也就是概率区间是{[0, 1/6], [1/6, 3/6], [3/6, 1]}。 计算的方法就是前缀和累加,也就是{1, 3, 6}。其中分母是不必要的。也就是说,构造区间的方法是:首先计算前缀和,然后根据前缀和来切分, 例如{3, 2, 4, 1}, 首先计算前缀和,得出{3, 5, 9, 10}, 然后就是区间{[0, 3][3, 5][5, 9][9, 10]}。

区间搜索:生成一个0到10之间的一个数x,那么首先要看所有区间的左端点,找到最后一个小于x的左端点。 在这时候,在进行一点优化,也就是说,{3, 5, 9, 10}信息已经够用了,只需要找到其中的一个点就可以了,这个点是第一个大于x的点,也就是所谓的lower_bound。

方法一:进行二分搜索。

方法二:根据有序快速的分治的建立平衡二叉搜索树,然后对x进行搜索,如果发现当前结点比x小,由于需要找比x大的数,因此向右侧走,反之,记录下来作为候选者,并向左侧走,因为左侧更小,需要找到第一个比x大的数。

1385. Find the Distance Value Between Two Arrays

题意:给出两个整数数组,求数组1中,满足条件的的元素个数,条件就是这个元素与数组2的所有元素的差值的绝对值都大于 给出的值d。

:暴力求解就是双层循环,时间复杂度O(N^2)。 优化解法是,先对数组2进行排序。这样,数组1里面每个元素只需要对数组2做两次二分搜索,就能知道这个元素存不存在差值绝对值都大于d 的情况了。例如,对于元素8,数组2为{1, 8, 9, 11},d=2。其中,左右两端都是满足条件的,但是 并不代表中间元素也满足条件。实际上,能够和8组合形成<=d的数的范围就是[6, 10],现在需要做的就是 寻找数组2中是否有元素落入这样一个区间:[6, 10], 也就是[8 - d, 8 + d]。 可以使用二分法lowerbound找出第一个不小于6的值的下标,然后使用upperbound找出第一个大于10的下标,如果这两个下标大小不等, 也就是中间有值的时候,就是找到了这样的数,所以就不满足条件。

PS.(1)lowerbound(大于等于x的第一个数)的理解就是比这个数x小的区间的边界;upperbound(大于x的第一个数)就是比x大的数的区间边界。在递增的情况下, lowerbound找到的就是右边界,upperbound找到的是左边界。

(2)c++迭代器操作:迭代器之间可以进行相减操作,得出相对两个迭代器相对距离,但不能进行相加操作,因为会溢出。 迭代器也可以直接加上或减去一个整数得出相对距离的迭代器,但是这个相对位置的迭代器必须要存在。