google 2016全职电面面经

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. }

复制代码

warriorbrant 发表于 2016-11-3 04:27
我不知道这是不是叫linear hashing，就是把原数组当成hash数组

好强大。big cong，你这咋想出来的。

warriorbrant 发表于 2016-11-3 04:27
我不知道这是不是叫linear hashing，就是把原数组当成hash数组

what if tmp is huge....

denev2004 发表于 2016-11-3 08:40
what if tmp is huge....

it only works for number from 1 to n

可以看这里， http://www.geeksforgeeks.org/fin ... s-in-a-given-array/

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

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

primbo 发表于 2016-11-3 09:00
it only works for number from 1 to n

你的原题有范围限制吗，要没有还真不好做

warriorbrant 发表于 2016-11-3 09:37
你的原题有范围限制吗，要没有还真不好做

同学面的google的题，他没有听清，要没限制真的没法做了感觉。