logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
why is this e-ink reader so cheap?
avatar
why is this e-ink reader so cheap?# PDA - 掌中宝
v*a
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.
avatar
q*x
3 楼
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.
avatar
a*m
4 楼
差不多吧。也不算特别便宜，当然这价格不错，俺要是在天朝可能仅收不住诱惑。
avatar
c*v
5 楼
ding....
avatar
f*0
6 楼
价格狠给力啊，不过最好的电子书汉王e920，都出来很久了价格还依然坚挺
avatar
q*c
7 楼
what's the data type? string, int, double, ...?
avatar
v*e
8 楼
前几天看了个新闻，iphone的套子背面都加上eink屏了，这样可以经常换换图案
avatar
s*n
9 楼
这个考古前面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.
avatar
q*c
10 楼
For integers, can do it in O(n) for sure.
avatar
r*t
11 楼
"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.
avatar
b*e
12 楼
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];
}
avatar
v*a
13 楼
how to do it?
please specify, please.

【在 q********c 的大作中提到】
: For integers, can do it in O(n) for sure.
avatar
q*c
14 楼
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;
}
avatar
m*0
15 楼
这个方法不错，觉得本质上和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;
avatar
q*c
16 楼
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.
avatar
q*x
17 楼
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;
avatar
q*c
18 楼
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.
avatar
q*x
19 楼
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.
avatar
q*c
20 楼
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.
avatar
q*x
21 楼
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.
avatar
r*t
22 楼
面官估计水平没到这个地步，别争了，以前也有类似状况过。

【在 q****x 的大作中提到】
: check clrs. your bit map is actually direct addressing, which is the
: primitive of hash table.
:
: could
相关阅读
百度云上的大文件怎么下载火柴绕不过IP限制？[KJPT]手机专利哪家强？诺基亚遥遥领先 (转载)哪里可以找到海外可用的电视家频道真心不喜歡Htc one m8乐视盒子 看最新的内地电影 用什么 APP 比较好？入了Lenovo的s8-50 感觉还不错求最便宜的方法keep一个手机号我只想要苹菓加一个工能重新评价一下Fire phoneverizon note 4 150了，最新的Google Voice收发短信是免费吗？请教高人：unlock Huawei mate 2还在合同内的ATT电话 如何解锁？求tmobile smartphone(Houston)帮忙推荐适合老人用的智能手机Lenovo s8-50还是MeMO Pad 7"有要one plus invite的吗？10个包子一个icefilms挂了么？回国买哪个版本的华为Mate 7带回来?
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。