H******7
发帖数: 1728 | 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*******4
发帖数: 1401 | 2 用一个vector作为hashmap的value保存positions？ | g*********s
发帖数: 1782 | 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****z
发帖数: 666 | 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*********s
发帖数: 1782 | 5 sorry i didn't notice positions. changed.
【在 S****z 的大作中提到】
: 找到一个就break？最后返回一个int？
: 题目不是说positions吗？
:
: thoughts
| S**I
发帖数: 15689 | 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*********s
发帖数: 1782 | 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******7
发帖数: 1728 | 8 than you you all. These really nice. | c******t
发帖数: 391 | 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; i
hm[arr[i]]++;
}
hash_map::iterator it;
int dup=0;
for(int i=0; i
it=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");
} |
|
