Google电面，面经

hackenkreuz 发表于 2015-10-11 01:46
怎么没人支持这楼，这个方法很好啊!

我仔细又想了一下我的这个方法其实不太好，如果相邻两个数差别很大的时候复杂度最坏情况是n*nlogn  反而比brute force还差

八月槎 发表于 2015-10-11 08:48
我仔细又想了一下我的这个方法其实不太好，如果相邻两个数差别很大的时候复杂度最坏情况是n*nlogn  反而 ...

那种情况是不是就是每个新数都会导致两个heap内容发生全部交换？

readman 发表于 2015-9-30 09:45
第二题不能用treeset么

这个是要求一个数是在BST排第几吧。无法treeset

goo 发表于 2015-10-10 20:16
stl set里怎么算出前面的个数啊？  lower_bound() 可以返回大于等于的第一个元素的iterator,然后怎么算出 ...

我的错，我当时想着直接用迭代器相减，现在想想是不行的。。。不支持RB tree的迭代器

第二题可以用splay tree， 每个node加上size的属性。Insert之后，刚刚insert的node是在root的位置上，而且时间是O(lgN) 。所以总时间是O(NlgN)

mileschen2008 发表于 2015-10-1 04:16
你这个复杂度应该是O(n^2)了吧？

用TreeSet的复杂度是NlogN 最好的了

最外层从0-n

然后每次获取tailSet 要logN
总共是NlogN

有点tricky的地方是遇到重复的怎么办?

1. 每次在添加新元素进treeset时 检查一下有没有存在
    如果存在 count++;

2. 最终output[i]=tailSet.size()+count;(output是最后的leftPass，count是重复元素   tailSet= treemap.tailSet(number, false) 可得小于number的所有数字集合)

pigmightfly 发表于 2015-10-10 23:04
不太懂这个思路。。
看上去是二分查找的模板，但是二分查找的前提条件是sorted array。
能否稍微讲一下 ...

(⊙o⊙)…审题有问题，请忽略。。。

yyboyz 发表于 2015-10-14 06:30
用TreeSet的复杂度是NlogN 最好的了

最外层从0-n

你这个count不行吧，因为你得求整个array的left pass。

mileschen2008 发表于 2015-10-15 03:59
你这个count不行吧，因为你得求整个array的left pass。

count统计的就是当前元素之前 已经出现的元素重复次数