r***u
发帖数: 241 | 1 问了问做过的projects，再问问了解哪些语言，问了C++的virtual function。
最后问了一个算法题，找出一个整数数组中第一个不重复的元素的index。
我回答用两个hashtable，一个存放unique elements，一个存放repeated elements。
有没有更好的办法？ |
f**h
发帖数: 1149 | |
r***u
发帖数: 241 | 3 webkit team
【在 f**h 的大作中提到】
: 什么职位？
|
h**k
发帖数: 3368 | 4 hash map, 记录出现的次数。
【在 r***u 的大作中提到】
: 问了问做过的projects，再问问了解哪些语言，问了C++的virtual function。
: 最后问了一个算法题，找出一个整数数组中第一个不重复的元素的index。
: 我回答用两个hashtable，一个存放unique elements，一个存放repeated elements。
: 有没有更好的办法？
|
p********7
发帖数: 549 | 5 bitmap 就可以了，都不用记录次数，2个bit就表示一个整数，0表示没有，1表示出现
一次，多余一次就是2了。
遍历一次之后再遍历第二次，第一个次数是1的就是答案 |
x******3
发帖数: 245 | 6 这个方法好，programming perl上是不是有讲到这个？
【在 p********7 的大作中提到】
: bitmap 就可以了，都不用记录次数，2个bit就表示一个整数，0表示没有，1表示出现
: 一次，多余一次就是2了。
: 遍历一次之后再遍历第二次，第一个次数是1的就是答案
|
p********7
发帖数: 549 | 7 是的
【在 x******3 的大作中提到】
: 这个方法好，programming perl上是不是有讲到这个？
|
v********w
发帖数: 136 | 8 how about starting from end and traversing back to the begining, record the
latest element which appears once once
in this way, we need only use 1 bit for each integer and only one traverse
【在 p********7 的大作中提到】
: bitmap 就可以了，都不用记录次数，2个bit就表示一个整数，0表示没有，1表示出现
: 一次，多余一次就是2了。
: 遍历一次之后再遍历第二次，第一个次数是1的就是答案
|
r***u
发帖数: 241 | 9
the
how do you maintain this information?
【在 v********w 的大作中提到】
: how about starting from end and traversing back to the begining, record the
: latest element which appears once once
: in this way, we need only use 1 bit for each integer and only one traverse
|
v********w
发帖数: 136 | 10 Given a[n]
int *p=&a[n-1];
hashtable(or bitmap) ht;
for i=n-2:-1:0
if ht.contians(a[i])
{if (a[i]==*p) p=0;}
else {p=&a[i];ht.add(a[i]);}
if (p) return *p
else noelementIndicator
【在 r***u 的大作中提到】
:
: the
: how do you maintain this information?
|
