v********a
发帖数: 14 | 1 Merge two unsorted array. Each array has unique values, but there are
dupliates between two arrays. Remove the duplicates and merge them. Time
complexity must be better than O(nlogn). You shouldn't use hash table. |
q****x
发帖数: 7404 | 2 no way, unless count sort applicable.
【在 v********a 的大作中提到】
: Merge two unsorted array. Each array has unique values, but there are
: dupliates between two arrays. Remove the duplicates and merge them. Time
: complexity must be better than O(nlogn). You shouldn't use hash table.
|
c**v
发帖数: 9 | |
q********c
发帖数: 1774 | 4 what's the data type? string, int, double, ...? |
s***n
发帖数: 373 | 5 这个考古前面bloomberg的题吧
记得后面跟贴说，一个array远长于另外一个
这样sort short array first, O(MlogM)
search in short array N*log(M)
if N>>M, close to O(N)
【在 v********a 的大作中提到】
: Merge two unsorted array. Each array has unique values, but there are
: dupliates between two arrays. Remove the duplicates and merge them. Time
: complexity must be better than O(nlogn). You shouldn't use hash table.
|
q********c
发帖数: 1774 | 6 For integers, can do it in O(n) for sure. |
r****t
发帖数: 10904 | 7 "no hash table" means literally no hash table, or any space cost is allowed?
【在 v********a 的大作中提到】
: Merge two unsorted array. Each array has unique values, but there are
: dupliates between two arrays. Remove the duplicates and merge them. Time
: complexity must be better than O(nlogn). You shouldn't use hash table.
|
b*****e
发帖数: 131 | 8 Time: O((m+n)logn)
Space: O(1)
using namespace std;
void union(int* a, int m, int* b, int n, int* res, int &len)
{
if(m < n) {
swap(a, b);
swap(m, n);
}
sort(b, b+n);
int* p;
for(int i = 0; i < m; i++) {
p = find(b, b+n, a[i]);
if(p != b+n)
*p = INT_MIN;
}
copy(a, a+m, res);
len = m;
for(int i = 0; i < n; i++)
if(b[i] != INT_MIN)
res[len++] = b[i];
} |
v********a
发帖数: 14 | 9 how to do it?
please specify, please.
【在 q********c 的大作中提到】
: For integers, can do it in O(n) for sure.
|
q********c
发帖数: 1774 | 10 Basic idea is use bit map.
Assume the max of the two arrays is Max. If it's not given, it can be
found
in linear time.
int* merge(int* a, int len1, int* b, int len2)
{
int[] array = new int[Max];
for(int i = 0; i < len1; ++i)
{
array[a[i]] = 1;
}
for(int i = 0; i < len2; ++i)
{
if(array[b[i]] != 1)
{ array[b[i]] = 1; }
}
int num = 0;
for(int i = 0; i < Max; ++i)
{
if(array[i] == 1)
{ num++; }
}
int[] list = new list[num];
int j = 0;
for(int i = 0; i < Max; ++i)
{
if(array[i] == 1)
{
list[j++] = i;
}
}
return list;
} |
|
|
m*********0
发帖数: 46 | 11 这个方法不错，觉得本质上和hash table一个思路。如果integer是long的话，extra
space可能会非常大。
有个简单的想法，先分别sort两个数组，O(nlogn) + O(mlogm). 然后merge，需要O(m+
n).
found
【在 q********c 的大作中提到】
: Basic idea is use bit map.
: Assume the max of the two arrays is Max. If it's not given, it can be
: found
: in linear time.
: int* merge(int* a, int len1, int* b, int len2)
: {
: int[] array = new int[Max];
: for(int i = 0; i < len1; ++i)
: {
: array[a[i]] = 1;
|
q********c
发帖数: 1774 | 12 Unique values should be a trigger to use bit map. It's the simplest form of
hashtable, but nobody would say it's a real hashtable. |
q****x
发帖数: 7404 | 13 not O(n) + O(1).
found
【在 q********c 的大作中提到】
: Basic idea is use bit map.
: Assume the max of the two arrays is Max. If it's not given, it can be
: found
: in linear time.
: int* merge(int* a, int len1, int* b, int len2)
: {
: int[] array = new int[Max];
: for(int i = 0; i < len1; ++i)
: {
: array[a[i]] = 1;
|
q********c
发帖数: 1774 | 14 What are you trying to say quantx? Are you saying linear time and no extra
space? If so, no-extra space is not required in the problem. |
q****x
发帖数: 7404 | 15 what you use is hash table.
【在 q********c 的大作中提到】
: What are you trying to say quantx? Are you saying linear time and no extra
: space? If so, no-extra space is not required in the problem.
|
q********c
发帖数: 1774 | 16 I already said, it's NOT a real hashtable. Although theoretically you could
call bit map a hashtable, nobody would talk like this in real coding. |
q****x
发帖数: 7404 | 17 check clrs. your bit map is actually direct addressing, which is the
primitive of hash table.
could
【在 q********c 的大作中提到】
: I already said, it's NOT a real hashtable. Although theoretically you could
: call bit map a hashtable, nobody would talk like this in real coding.
|
r****t
发帖数: 10904 | 18 面官估计水平没到这个地步，别争了，以前也有类似状况过。
【在 q****x 的大作中提到】
: check clrs. your bit map is actually direct addressing, which is the
: primitive of hash table.
:
: could
|
