一道某搜索公司的onsite题

chenxiaocong 发表于 2017-11-23 23:59
我的想法是，
1.把主视图由低到高排序，得到一个数组heights，然后再存一个sums数组，每一位是相对应heigh ...

这个解法好厉害啊..
相当于利用主视图来进行当前最优解，然后再利用左视图，在里面找左视图当前点那行的最优值..
点赞..

chenxiaocong 发表于 2017-11-23 23:59
我的想法是，
1.把主视图由低到高排序，得到一个数组heights，然后再存一个sums数组，每一位是相对应heigh ...

可以讲讲这么做的理由吗？没太看懂老实讲

貌似突然想明白了 这个相当于在主视图那块准备了不同高度的面包切片 然后从组合起来左视图那块选出高度符合要求的面包片

15daysleft 发表于 2017-11-24 06:36
你这个做法是对的 也是当时我最先想出来的做法
然后面试官说还可以继续优化到不需要sum数组。。我当时就 ...

求问大佬，如果n是边长的话，主视图和左视图都有n个元素，按照大佬的思路排好顺序后，每个左视图对应的主视图都要向右扫一遍，时间为O(n), 一共有n个左视图， 总的Worst Case时间复杂度为O(n^2), 请问大佬是怎么分析出O(nlogn)的？ 求指教

大佬的想法你不懂的 我懂了已经

chenxiaocong 发表于 2017-11-23 23:59
我的想法是，
1.把主视图由低到高排序，得到一个数组heights，然后再存一个sums数组，每一位是相对应heigh ...

这个解法很棒， 想请问复杂度O(NlogN)是为什么呀？排序和二分查找一共的复杂度？

饶有兴致的写了一下代码，复杂度是 O(klogk) where k = max(m, n)
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_area = 0, rolling_sum = 0, acc_sum = 0;
  sort(main_view.begin(), main_view.end());
  sort(left_view.begin(), left_view.begin());

  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(left_view[j] <= main_view[i] && j < m) {
                  max_area += rolling_sum;
                  j++;
          }
  }
  return max_area;
}

kyo 发表于 2017-11-24 08:59
求问大佬，如果n是边长的话，主视图和左视图都有n个元素，按照大佬的思路排好顺序后，每个左视图对应的主 ...

不用 排好序后总共扫一遍就行了 类似于merge two sorted arrays

chenxiaocong 发表于 2017-11-23 23:59
我的想法是，
1.把主视图由低到高排序，得到一个数组heights，然后再存一个sums数组，每一位是相对应heigh ...

左视图[5，4，3]， 主视图[5, 3, 1]。 先排序主视图得[1, 3, 5], sums是[3, 7, 9] (例如7是1+3+3), 所以最后最大总体积/高度是 9+9+7=25吗？

一种可能的矩阵：
1 3 5
1 3 4
1 3 3
左视图：[5，4，3]
主视图：[1，3，5]

mark一下，关注楼主后续