一道M$算法题。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道M$算法题。

一道M$算法题。# JobHunting - 待字闺中

H*72011-02-09 08:02

1 楼

Consider array of INT of positive numbers:
{1,3,6,4,7,6,9,2,6,6,6,6,8}
Given: only one number is repeated, return number and positions with
efficient algorithm.
Any ideas for efficient algorithms?
如果用hash map的话，怎么维护indices?　因为需要返回positions...any thoughts?

f*42011-02-09 08:02

2 楼

用一个vector作为hashmap的value保存positions？

g*s2011-02-09 08:02

3 楼

?
using namespace std;
vector find_duplicate_idx(const vector& A)
{
unsorted_map X;
vector idx;
for ( int i = 0; i < A.size(); ++ i ) {
unsorted_map::iterator it = X.find(A[i]);
if ( it != X.end() ) {
idx.push_back((*it).second);
break;
}
else X[A[i]] = i;
}
return idx;
}

【在 H******7 的大作中提到】

: Consider array of INT of positive numbers:
: {1,3,6,4,7,6,9,2,6,6,6,6,8}
: Given: only one number is repeated, return number and positions with
: efficient algorithm.
: Any ideas for efficient algorithms?
: 如果用hash map的话，怎么维护indices?　因为需要返回positions...any thoughts?

S*z2011-02-09 08:02

4 楼

找到一个就break？最后返回一个int？
题目不是说positions吗？

thoughts

【在 g*********s 的大作中提到】

:
: ?
: using namespace std;
: vector find_duplicate_idx(const vector& A)
: {
: unsorted_map X;
: vector idx;
: for ( int i = 0; i < A.size(); ++ i ) {
: unsorted_map::iterator it = X.find(A[i]);
: if ( it != X.end() ) {

g*s2011-02-09 08:02

5 楼

sorry i didn't notice positions. changed.

【在 S****z 的大作中提到】

: 找到一个就break？最后返回一个int？
: 题目不是说positions吗？
:
: thoughts

S*I2011-02-09 08:02

6 楼

make some changes on your code, a little more efficient:
using namespace std;
list find_duplicate_idx(const vector& A)
{
hash_map X;
list idx;
for ( int i = 0; i < A.size(); ++ i ) {
hash_map::iterator it = X.find(A[i]);
if ( it != X.end() ) {
idx.push_back(it->second);
idx.push_back(i);
for ( int j = i + 1; j < A.size(); ++j )
if ( A[j] == A[i] )
idx.push_back(j);
return idx;
}
X[A[i]] = i;
}
return idx;
}

【在 g*********s 的大作中提到】

: sorry i didn't notice positions. changed.

g*s2011-02-09 08:02

7 楼

yes this is better.

【在 S**I 的大作中提到】

: make some changes on your code, a little more efficient:
: using namespace std;
: list find_duplicate_idx(const vector& A)
: {
: hash_map X;
: list idx;
: for ( int i = 0; i < A.size(); ++ i ) {
: hash_map::iterator it = X.find(A[i]);
: if ( it != X.end() ) {
: idx.push_back(it->second);

H*72011-02-09 08:02

8 楼

than you you all. These really nice.

c*t2011-02-09 08:02

9 楼

How about this one? Is this O(NlogN) solution?
#include
#include
using namespace std;
void finddup(int arr[], int length){
hash_map hm;
cout<for(int i=0; ihm[arr[i]]++;
}
hash_map::iterator it;
int dup=0;
for(int i=0; iit=hm.find(arr[i]);
if(it->second>1){
dup=it->first;
cout<}
}
cout<}
void main(){
int arr[]={1,2,3,5,4,6,6,7,6,8,9,10};
finddup(arr,sizeof(arr)/sizeof(int));
system("pause");
}