BYR Achieve · 镜像论坛

微软拔树题O(n)的解法 -Java版

2018/4/4镜像同步13 回复

暴力解法在这种极端情况下会超时。 Example：{ 1, 9, 8, 7, 6, 5, 4, 3, 2} 每一次的遍历只能让数组规模减1，所以总共要遍历（n-1）次，而每次遍历的规模为整个数组长度，即n+(n-1)+(n-2)+(n-3)+……+2 所以总的时间复杂度为O(n2/2) 非暴力解法如下。 plantHeight[]是表示植株长度的数组。 numOfPlants表示植株的数目。 f(i):记录着位置i会在第几天被拔出。 p[i]:记录着从第i个位置往前数，找到的第一个比a[i]小的元素的位置。若a = {1，2，9，5，7，6}，则p = {-1，0，1，1，3，3} 当遍历完一次数组a, 得到数组p，只需要O(n)的时间复杂度. m[i]:记录着从i位置到p[i]处的区间内当中的植株最晚会被拔出的时间，也就是最大的f值 m[i]=max(f[j]) j∈(p[i]，i) //此处为开区间推理得，第i个位置的植株要等待区间(p[i]，i)内的植株都被拔除后，才会被拔除。因此，f[i] = m[i] +1; java代码如下： import java.io.*; import java.lang.Math; class test { public static void main (String[] args) { int[] a = {3,6,9,8}; int[] b = {3,2,1,2,3,2,1,5,4,3,2,1,5,4}; int[] c = {2,1}; int[] d = {1,5,4,3,5,4,5,3}; int[] e = {1, 7, 6, 5, 2, 6, 5, 4, 6, 5, 6, 3}; int A = numberOfDays(a,a.length); int B = numberOfDays(b,b.length); int C = numberOfDays(c,c.length); int D = numberOfDays(d,d.length); int E = numberOfDays(e,e.length); System.out.println(A+" "+B+" "+C+" "+D+" "+E); } public static int numberOfDays(int[] plantHeight,int numOfPlants) { int[] p = new int[numOfPlants]; int[] m = new int [numOfPlants]; int[] f = new int [numOfPlants]; p[0] = -1; m[0] = 0; f[0] = 0;// 表示不会被移除 for(int i = 1 ;i < numOfPlants;i++){ if(p[i] == -1) continue; int j = i-1; int max = 0; while(j >= 0){ if(plantHeight[j] < plantHeight[i]){ p[i] = j; m[i] = max; f[i] = max+1; break; } else { max = Math.max(f[j],max);//当前区间（p[j],j]中最大的f[j]值 j = p[j]; //继续搜索，跳到p[j]位置 } } if(j==-1)p[i] = j; } int res = 0; for(int k = 0; k < numOfPlants;k++){ res = Math.max(res,f[k]); } return res; } } 用了另一个楼主的测试用例，跑出来的答案是：2，4，0，4，4[ema0]

订阅后，新回复会通过你的通知中心匿名送达。