FB新鲜出炉的电面

zzz1322 发表于 2016-6-4 19:46
没有。一个二维平面上，给定N个点，求离原点最近的前K个点。

所以跟 LC的 215. Kth Largest Element in an Array   很像

laonawuli 发表于 2016-6-5 11:44
另外decode ways 是和LC上完全相同的返回所有可能性的数量int， 还是说返回所有结果List?

和LC完全相同

laonawuli 发表于 2016-6-5 11:52
所以跟 LC的 215. Kth Largest Element in an Array   很像

是的，很相似。不过O（n）的做法不太好写，边界很容易写错

zzz1322 发表于 2016-6-4 19:54
是的，很相似。不过O（n）的做法不太好写，边界很容易写错

卧槽这题怎么O(n)? 不应该是 nLogn么

补充内容 (2016-6-4 19:58):
说错  nLogK

laonawuli 发表于 2016-6-5 11:57
卧槽这题怎么O(n)? 不应该是 nLogn么

补充内容 (2016-6-4 19:58):

估计楼主说错了，heap 的 time complexity 和 quick select一样。。。。

laonawuli 发表于 2016-6-5 11:57
卧槽这题怎么O(n)? 不应该是 nLogn么

补充内容 (2016-6-4 19:58):

nlogk是用堆的，O(n)的是用快排的partition。每次随机抽取一个元素，把数组分为小于这个元素和大于这个元素的两个部分，这样，由于是随机的抽取的，期望就是把数组平均分成两半，所以T(n) = T(n / 2) + O(n)。根据主定理，T(n) = O(n)。可以参考一下我LC这道题的代码。

1. import java.util.Random;
   
2. 
   
3. public class Solution {
   
4.    
   
5.     Random r = new Random();
   
6.    
   
7.     private void swap(int[] nums, int i, int j) {
   
8.         int t = nums[i];
   
9.         nums[i] = nums[j];
   
10.         nums[j] = t;
    
11.     }
    
12.    
    
13.     private int kth(int[] nums, int left, int right, int k) {
    
14.         int i = left, n = right;
    
15.         int mid = r.nextInt(right - left + 1) + left;
    
16.         int pivot = nums[mid];
    
17.         for(int j = left; j <= n;) {
    
18.             if(nums[j] > pivot) swap(nums, i++, j++);
    
19.             else if(nums[j] < pivot) swap(nums, j, n--);
    
20.             else ++j;
    
21.         }
    
22.         if(k + left < i) return kth(nums, left, i - 1, k);
    
23.         else if(k + left <= n) return nums[k + left];
    
24.         else return kth(nums, n + 1, right, k - (n - left + 1));
    
25.     }
    
26.    
    
27.     public int findKthLargest(int[] nums, int k) {
    
28.         return kth(nums, 0, nums.length - 1, k - 1);
    
29.     }
    
30. }

复制代码

zzz1322 发表于 2016-6-4 20:03
nlogk是用堆的，O(n)的是用快排的partition。每次随机抽取一个元素，把数组分为小于这个元素和大于这个元 ...

确实比heap复杂多了。你当时用的heap还是partition？另外为毛给你搞了两轮电面。。。

补充内容 (2016-6-4 20:14):
看到你上面说了用heap了

zzz1322 发表于 2016-6-5 12:03
nlogk是用堆的，O(n)的是用快排的partition。每次随机抽取一个元素，把数组分为小于这个元素和大于这个元 ...

Parition 是N time 吧， 因为可以recursion，所以是nlgn， 堆的话，先push进去所有元素 nlgn time，再找kth KnLgn 吧。。。怎么突然感觉这么凌乱

zzz1322 发表于 2016-6-5 11:50
一个pointer不是最佳的方案。我说了这个方案，貌似小哥很不满意，问我有没有其他的方案，我想了半天没想 ...

这道题不就是Move zeroes么，为什么你的test case是这个结果...