Facebook onsite

psyclaudeZ 发表于 2014-10-30 17:36
第二题如果不需要结果有序的话堆都用不着……直接上selection algorihtm, 选出跟target差绝对值第k大元素， ...

我也觉得要的应该是这种解吧

22691482 发表于 2014-11-4 16:46
先根据target把数组换成diff (in place).
然后用quick select 找到the kth smallest.
然后再partition

b比较的是绝对值的差 所以没办法in place还能恢复的吧

jg7933 发表于 2014-11-18 19:58
quick select的java 代码哪里找的到例子吗？感觉自己写不出来。。。

刚才写的
public int quickSelect(int[] a, int start, int end, int k) throws Exception {
                if (end - start + 1 < k)
                        throw new IllegalArgumentException();
                int pivot = a[start];
                int p1 = start + 1;
                int p2 = end;
                while (true) {
                        while (p1 <= end && a[p1] <= pivot)
                                ++p1;
                        while (p2 >= start && a[p2] > pivot)
                                --p2;
                        if (p1 > p2)
                                break;
                        swap(a, p1, p2);
                        ++p1; --p2;
                }
                swap(a, start, p2);
                if (p1 - start == k)
                        return pivot;
                if (p1 - start < k)
                        return quickSelect(a, p1, end, k - (p1 - start));
                return quickSelect(a, start, p2, k);
        }

dtcxzch 发表于 2014-12-5 16:09
刚才写的
public int quickSelect(int[] a, int start, int end, int k) throws Exception {
                if (end ...

worst case n^2?

davidwh 发表于 2014-12-7 14:18
worst case n^2?

恩对啊 和quicksort一样， 不过可以优化一下

王可雪 发表于 2014-10-31 04:26
array.map(abs(self - given number))
Then use min heap

max heap

第二题代码，请大神们指教

struct Node
{
    int val;
    int index;
    Node(int val_, int index_):val(val_), index(index_)
    {
    }
    bool operator<(const Node& n1) const
    {
        return val>n1.val;
    }
};
vector<int> FindKClosest(vector<int> a, int k, int x)//, 0<=k<=a.size()
{
    //for(auto &i: a) i=abs(i-x);
    vector<Node> v;
    for(int i=0;i<a.size();i++)
    {
        Node n({abs(a[i]-x), i});
        v.push_back(n);
    }
    priority_queue<Node> pq(v.begin(), v.end());
    //for(auto i: v) pq.push(i);
    vector<int> ans;
    //cout<<k<<endl;
    for(int i=0;i<k;i++)
    {
        ans.push_back(a[pq.top().index]);
        pq.pop();
    }
    return ans;
}

不对 上面这个算法是O(n+klogn)的，空间O(n), 其实如果 不需要返回k个数的顺序的话，其实只要直接On的quickselect就可以了，之前以为只能用来找第k个数，其实找到的同时也做了partition，前k小的都在左边了，后面的都在右边了，因此和quickselect是一样的，时间复杂度O(n)，空间是O(n)，开一个新的数组表示差值执行quickselect，还有一个递归栈，最坏O(n), 时间不差于之前那个算法，甚至可能更好。

int Partition_InOrder(vector<pair<int, int>> &a, int low, int high)
{//inorder
    int i=low, j=high;
    pair<int,int> pivot=a[low];
    while(i<j)
    {
        while(i<j && a[j].first >= pivot.first) j--;
        while(i<j && a[i].first <= pivot.first) i++;
        if(i<j) swap(a[i], a[j]);
    }
    swap(a[i], a[low]);
    return i;
}

int QuickSelect(vector<pair<int, int> >& a, int low, int high, int k)//select kth smallest, or inorder kth ele
{// 1<=k<=high-low+1, low<=high
    if(low>high) return -1;
    int mid=Partition_InOrder(a, low, high);
    int prelen=mid-low+1;
    if(prelen==k) return a[mid].first;
    else if(prelen > k)
        return QuickSelect(a, low, mid-1, k);
    else
        return QuickSelect(a, mid+1, high, k-prelen);
}

vector<int> FindKClosest_QuickSelect(vector<int>& a, int k, int x)
{
    int n=a.size();
    if(k==n) return a;
    vector<pair<int, int>> v;
    for(int i=0;i<n;i++) v.push_back({abs(a[i]-x), i});
    QuickSelect(v, 0, n-1, k+1);
    vector<int> ans;
    for(int i=0;i<k;i++)
        ans.push_back(a[v[i].second]);
    //vector<int> ans(a.begin(), a.begin()+k-1);
    return ans;
}

ccgogo123 发表于 2014-10-30 18:17
没错，有个朋友面另外一家公司，要求返回前k小的元素，不许用heap，就要用quickselect。

真的要用quickselect吗？感觉面试好少用到这个

王可雪 发表于 2014-10-30 15:26
array.map(abs(self - given number))
Then use min heap

应该用max heap，保持heap大小为k，这样时间复杂度只有(nlogk)