阅读以下文章,首先至少要求通过一道分治法的题目或听过一道该类型的讲解。
对于分治的题目,想必你应该知道,通常我们是对于一个区间拆分两个部分,而最小子问题通常是只包含一个元素的区间数组。为了后续方便处理更大范围的区间,通常在处理该小区间后,我们会将其区间内元素排序,例如下面例子:
该例子是求:对于右区间的每个元素,求右侧大于左侧的元素个树,比如左数组为 2 3 右数组为:4 3,那么对于4来说2 3 两个都比4小,对于右侧的3来说只有2比他小,所以结果为3
很显然,我们可以使用两个指针,暴力遍历所有,直接求出答案,而该代码的时间复杂度为O( n 2 n^2 n2)
public static int GetKey(){int res=0;for(;left<mid=;left++){for(;right<=n;right++){ //n为区间最右端res+=num[right]>num[left]?1:0; //满足则加1,不满足则不加}}return res;
}
在一次期末考试后,班主任决定颁发奖励,满足一定方式的学生都可以获得某个等级的奖励,对于分数高的同学既可以获取一等奖,也可以获取二,三等奖。聪明的班主任想到快速的方法分配奖励,他先将分数从低到高排序,他先从低级奖励分配,每次分配奖励,他先看看学生的分数,由于学生分数以排序,从左往右数,直到找到满足分数的学生,剔除前面的学生,毕竟连当前奖励分数都不满足,那么必定与后面的奖励无缘了,每分配下一等级的奖励,他都循环这一步骤。
这个故事是有一定的开导性的。
自然可以想到一种更好的方法了(对于有单调性的题目一般都可以,所谓单调性是:如果a>b,b>c,一定有a>c)
那就是左右两侧都先排序,利用有序性,则可以减少大部分的计算,例如下图1.右指针指向的元素是大于左指针指向的元素,由于排序后,右指针后面的其实都大于左指针指向的元素,所以大于23的右侧元素个数为区间右端减去右指针再加1。
2.然而聪明的你意思到,这并不对,因为你怎么确定右指针的左侧不会有比23大的树呢,其实对于左右指针的控制确保了右指针的前面不会存在比左指针大的情况的。
public static int GetKey(){for(;left<=mid;left++){ //遍历每一个需要满足的条件while(right<n&&num[right]<=num[left]){ //向右寻找满足条件的元素right++; }if(right<n){ //如果有满足元素的话res+=n-1-right+1; //n-1代表区间最右下标}else{break; //当前过滤的没有满足的元素了,那么后面更不可能了}} return res;
}
仔细观察该代码,是不是发现右指针前面的元素一定不会大于左指针的呢!
刚学完,来试试可不可以立即想到一种解决方案,毕竟不是所有题的单调性都是这么直观的。
数组还是上面的图片,但是条件换为num[left]>num[right]*2。
这与上面的题目类似,只不过是左右大小条件换了,变成左侧大于右侧,那么你可以把条件当作右侧,分数当作左侧(引用上面的故事)。
以下是答案
public static int GetKey(){for(;right<n;right++){int res=0;while(left<=mid&&num[left]<=num[right]){left++;}if(left<=mid){res+=mid-left+1;}}return res;
}