google 2016全职电面面经

google电面 挂掉了，问题和这个链接里的一模一样，我回答的心路历程也和这个一样。有大神知道

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

面试官说了，空间复杂度需要是O(1), 时间复杂度优于 O(n2)

primbo 发表于 2016-11-3 03:35
如果是1 到n之间的话怎么做？ conting sort也要占用空间的啊。

我不知道这是不是叫linear hashing，就是把原数组当成hash数组

1. public int helper(int[] array){
   
2.    int len=array.length();
   
3.    for(int i=0;i<len;i++){
   
4.        int tmp=Math.abs(array[i]);
   
5.        if(array[tmp-1]<0)return tmp;
   
6.        else array[tmp-1]*=-1;
   
7.    }
   
8.    return -1;
   
9. }

复制代码

高票答案不可以么？不然linear probing? 开一个等size数组，h(x)+i是新的index, 插入是O(1),search找重复的的话h(x)+i (i=1,...,k).空间O(n)，时间的话看hash 函数选择，最差O(n)，平均O(1)。。。这个好像算法导论hash table实现有讲，不知道是不是面馆要的，遇上这种题目真是醉了 ...

找数组里面第一个重复的数字

难道面试官想让你排序？

shuiguo 发表于 2016-11-2 08:05
难道面试官想让你排序？

排序了找到的就不一定是第一个重复的了。不可以排序

elizabethxiazhi 发表于 2016-11-2 04:27
高票答案不可以么？不然linear probing? 开一个等size数组，h(x)+i是新的index, 插入是O(1),search找重复的 ...

空间复杂度需要为O(1)

让走过的array有序，用binary search找到相邻数字然后insertion？
问题就是insertion的worst case会O（n2）

数组中element的值有范围限制么

如果元素范围在1-n之间我知道咋做，n是length

warriorbrant 发表于 2016-11-2 13:11
如果元素范围在1-n之间我知道咋做，n是length

如果是1 到n之间的话怎么做？ conting sort也要占用空间的啊。