Google 两道题

1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
，矩形的4个角都是1.

leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满意。不知道有没有复杂度更少的算法。

2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数目。之后把队打乱，跟据高度和比自己高的人的数目还原原来的队列。

我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的算法。

想法是这样，首先将所有人排个序，从小到大，从最矮的开始往园数组插，
对于位置在原数组位置x的人，他前面有n个人比他高，而比他矮的人都已经放到位了，比他高的人都还没放，所以我们就数空位从前数n个，已经放了人的地方跳过，那就得到x了。

但是这样的做法是n^2（在放数找位置这一步需要O（n）的时间）有人提如果用interval tree存空格的话找到第K个空格只需要O（lgn）时间，那么总的复杂度就是O（nlogn）。

Interval tree 找第k个空格的用法

Every node stores the number of open spaces at its range, we will be able to locate the kth empty space in lgn time （the above image has node that stores the minmum element of the range, we change that to the number of free spaces, and update corresponding spaces when every we do insert).

 

From:

https://hellosmallworld123.wordpress.com/2014/04/18/google%E4%B8%A4%E9%81%93%E9%A2%98/