一道某搜索公司的onsite题

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

改了一下code，请指教！！！


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]) {
                  int diff = main_view[i] - left_view[j];
                  max_val += (rolling_sum - diff * (n - j));
                  j++;
          }
  }
  return max_val;
}

补充内容 (2017-11-24 15:07):
那个main_view是main_view[i] 不知道为啥没显示。。

补充内容 (2017-11-24 15:07):
main view is main_view [  i  ]

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

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]) {
                  int diff = main_view[i] - left_view[j];
                  max_val += (rolling_sum - diff * (n - j));
                  j++;
          }
  }
  return max_val;
}

ICong 发表于 2017-11-24 14:57
嗯嗯 多谢回复，我的理解是左视图里的元素如果在正视图里不存在，就只能用naive的方法单独算，其他的可以 ...

不存在的话 不知道你是不是指的
  2  4  6               2  4  6
1              ---》1  1  1  1
3                     3  2  3  3
6                     6  2  4  6
就是不存在的吧。。？或者你可以举个例子？
首先看1， 1比主视图所有的都小 所以第一行只能填1 体积是 1 * 3
然后看3， 3只比2大 体积就是 2 + 3 * 2
最后看6， 6比2和4都大 体积就是 2 + 4 + 6 * 1
并不需要主视图里面刚好存在这个元素 在主视图里面找第一个>=左视图当前元素的index就可以了

ICong 发表于 2017-11-24 13:16
老哥你这test case不太对啊，不存在这样的城市，左视图中最大的9在主视图中没出现？

思路懂了就OK，不用在意这些细节，因为没意思

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

你是有多菜，都给你分析到这了，还有人给你code都写出来了，还说没有O(nlogn)的解法？？？？

kyo 发表于 2017-11-25 03:01
你是有多菜，都给你分析到这了，还有人给你code都写出来了，还说没有O(nlogn)的解法？？？？

戾气这么重干什么，不就是指出你test case有错吗？不会好好说话？

ICong 发表于 2017-11-25 11:44
戾气这么重干什么，不就是指出你test case有错吗？不会好好说话？

啊？？？大佬，不要玻璃心，只是说了下你不会分析时间复杂度。。。没有别的意思

5 4 3   8 3 2

想问问楼主都是哪些leetcode原题啊，什么难度的？

我就碰到了这道题，思路就是酱了，写了出来。