一道某搜索公司的onsite题

int max_volume(vector<int> main_view, vector<int> left_view){
  if(main_view.size() == 0 || left_view.size() == 0) return 0;
  int m = left_view.size(), n = main_view.size();
  int max_val = 0, rolling_sum = 0, acc_sum = 0;
  sort(main_view.begin(), main_view.end());
  sort(left_view.begin(), left_view.end());

  for(int i = 0, j = 0; i < n; i++){
          acc_sum += main_view[i];
          rolling_sum = acc_sum + (n - i - 1) * main_view[i];
         
          while(j < m && left_view[j] <= main_view[i]) {
                  max_val += rolling_sum;
                  j++;
          }
  }
  return max_val;
}

ICong 发表于 2017-11-24 09:10
这个解法很棒， 想请问复杂度O(NlogN)是为什么呀？排序和二分查找一共的复杂度？

想起来了，其实sort之后还是蛮简单的。可以用Binary Search + linear scan 做， 或者只用Linear scan（当然这个肯定是最优的）。 因为主左视图都已经sort了，每次从主视图里扫的时候，没有必要从头开始，啥意思呢：
比如sort后的左视图： [3, 5, 7, 9]  主视图为[2, 4, 6, 8]
a. 当前位置在左视图的3的位置， 开始扫主视图 2  < 3, 记录下来， 4 > 3 记录下来， 4以后的所有元素都不用扫，都比3大
b. 当前位置在左视图的5的位置, 我们前面扫过的数都没有必要再扫第二遍， 因为肯定比5小（因为左视图已经排序了），直接从4开始扫....So on and So forth

为什么单用Binary Search不能解决问题？
因为我们不光要知道有多少数比target小， 还要知道比它小的具体值是多少？
比如： 3, [2, 4, 6, 8]
这里我们知道4以后都比3大，但是还要看4以前的具体值，linear scan 4 以前的所有元素

总的时间复杂度：
sort 主左视图： nlogn + nlong
linear scan: O(n)
total: O(nlogn)

hychin 发表于 2017-11-24 09:20
饶有兴致的写了一下代码，复杂度是 O(klogk) where k = max(m, n)
int max_volume(vector main_view, vect ...

嗯！就是这个意思
（...面试的时候并没有写代码，那题研究了好久最终代码就这么几行 真是血亏）

15daysleft 发表于 2017-11-24 09:33
嗯！就是这个意思
（...面试的时候并没有写代码，那题研究了好久最终代码就这么几行 真是血亏 ...

妹妹已经很厉害啦，想到这么多思路，我已经感觉offer在路上了！

kyo 发表于 2017-11-24 09:32
想起来了，其实sort之后还是蛮简单的。可以用Binary Search + linear scan 做， 或者只用Linear scan（当 ...

老哥你这test case不太对啊，不存在这样的城市，左视图中最大的9在主视图中没出现？

感谢楼上大佬们提供的思路，但是顶楼的算法好像不太对，举一个test case：主视图【2，5，6】，左视图【1，4，6】，用最intuitive的算出来maxHeight 应该是26，用rolling sum的做法算出来则是31，我觉得面试官的思路应该不是这样的，或者压根这题就没NlogN的解法？

ICong 发表于 2017-11-24 13:29
感谢楼上大佬们提供的思路，但是顶楼的算法好像不太对，举一个test case：主视图【2，5，6】，左视图【1，4 ...

     2   5   6
1   1   1   1

4   2   4   4

6   2   5   6

上面加起来就是26啊

hychin 发表于 2017-11-24 13:35
2   5   6
1   1   1   1

确实是二十六，可是你实现的算法的结果好像是6 + 12 + 13 = 31。实际应该是3 + 10 + 13 = 26

ICong 发表于 2017-11-24 13:45
确实是二十六，可是你实现的算法的结果好像是6 + 12 + 13 = 31。实际应该是3 + 10 + 13 = 26

算法大体肯定不会有问题的..
不过这个code是有点bug
应该是leftview 和 mainview取更小的

15daysleft 发表于 2017-11-24 14:08
算法大体肯定不会有问题的..
不过这个code是有点bug
应该是leftview 和 mainview取更小的

嗯嗯 多谢回复，我的理解是左视图里的元素如果在正视图里不存在，就只能用naive的方法单独算，其他的可以用rolling sum加快？但是这样最优也许是O（NlogN），不能保证是这个复杂度吧？