facebook 实习 面经

songty11 发表于 2016-1-29 11:34
第二题这样是o(n)

你这个是nlogn 因为Lower_bound 是 “On average, logarithmic in the distance between first and last: Performs approximately log2(N)+1 element comparisons (where N is this distance).”
http://www.cplusplus.com/reference/algorithm/lower_bound/

小海 发表于 2016-2-4 08:49
你这个是nlogn 因为Lower_bound 是 “On average, logarithmic in the distance between first and last: ...

多谢指正！那就不用lower_bound，可以自己写一个比较的~因为数组里的元素不会多于3个...

singku 发表于 2016-1-27 13:38
实现了一下第二题的代码 应该可以跑

你好，打扰一下，能不能问一下为什么会需要这个条件判断语句啊
else if (nums[i] > nums[least] && nums[i] < nums[b]) {

a598165394 发表于 2016-2-10 23:11
你好，打扰一下，能不能问一下为什么会需要这个条件判断语句啊
else if (nums &gt; nums[least] &amp;&amp; nums &lt;  ...

因为least记录了最小值的位置，这个位置可能在ab这个升序对的后面，如果当前值大于最小值，而且小于b 需要更新升序对。ab始终是一个最低的升序对。

singku 发表于 2016-2-11 01:08
因为least记录了最小值的位置，这个位置可能在ab这个升序对的后面，如果当前值大于最小值，而且小于b 需 ...

我觉得或许用一个b和least两个变量应该就够了吧？

1.         public boolean secfind(int[] nums){
   
2.             int b,least;
   
3.             int i=0;
   
4.             while(i<nums.length-1&& nums[i]>nums[i+1]){
   
5.                 i++;
   
6.             }
   
7.             if(i>=nums.length-2) return false;
   
8.             b = i+1;
   
9.             least = i;
   
10.             for(i=i+2;i<nums.length;i++){
    
11.                 if(nums[i]>nums[b]) return true;
    
12.                 if(nums[i]<nums[least]) least = i;
    
13.                 if(nums[i]> nums[least] && nums[i]<nums[b]) b=i;
    
14. 
    
15.             }
    
16.             return false;
    
17.         }

复制代码

a598165394 发表于 2016-2-11 02:08
我觉得或许用一个b和least两个变量应该就够了吧？

你这样写是对的 不过第一个while里还是要 nums[i] >= nums[i+1]

我的做法额外用了一个a存升序的位置 你没存

singku 发表于 2016-2-12 08:02
你这样写是对的 不过第一个while里还是要 nums >= nums

我的做法额外用了一个a存升序的位置 你没存

好的嗯，谢谢了啊！祝找工作顺利！

第二题用一个空间为3的栈就行吧？
将第一个元素进栈，loop一遍数组，如果当前元素比栈顶小的话就退栈知道栈顶元素比当前元素小或栈空并将该元素进栈。当栈满表示已经有三个升序元素，返回true就行，复杂度O(n), O(1)

木易wen 发表于 2016-2-14 07:10
第二题用一个空间为3的栈就行吧？
将第一个元素进栈，loop一遍数组，如果当前元素比栈顶小的话就退栈知道 ...

这个是正解

小海 发表于 2016-2-4 08:49
你这个是nlogn 因为Lower_bound 是 “On average, logarithmic in the distance between first and last: ...

个人认为还是O(n) time complexity, 因为对于这里的log2(N) + 1， N永远小于3，所以可以认为是constant time