拿出芭蕉扇扇扇 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

拿出芭蕉扇扇扇

拿出芭蕉扇扇扇# Joke - 肚皮舞运动

r*l2011-01-25 08:01

1 楼

Given an unsorted array A[] with size (100 - k), the elements in the array
are unique numbers from 1 to 100.
Apparently there are k numbers are missing. Give a linear time and constant
space solution to find the k
missing numbers.
Any thoughts?

J*y2011-01-25 08:01

2 楼

在 Part 5, 如果我DIY １４０表 (没找律师)，我应该填２if a company 还是填：３
if an individual.
谢谢
Part 5. Additional information about the petitioner.
1. Type of petitioner
[x] Employer
[ ] Self
2. If a company, give the following:
Type of Business
Date Established (mm/dd/yyyy)
Current Number of Employees
Gross Annual Income
Net Annual Income
NAICS Code
DOL/ETA Case Number
3. If an individual, give the following:
Occupation
Annual Income

x*a2011-01-25 08:01

3 楼

以前同学读课文，其中有一句：拿出芭蕉扇扇扇。本来停顿应该是拿出芭蕉扇，扇扇。
那同学直接读成：拿出芭蕉，扇扇扇！

g*s2011-01-25 08:01

4 楼

Discussed in the last month. in-place swap the i to (i-1)-th of the array.

array
constant

【在 r****l 的大作中提到】

: Given an unsorted array A[] with size (100 - k), the elements in the array
: are unique numbers from 1 to 100.
: Apparently there are k numbers are missing. Give a linear time and constant
: space solution to find the k
: missing numbers.
: Any thoughts?

x*S2011-01-25 08:01

5 楼

Eb1B has to be sponsored by your employer.
So, Part 5
you should fill out the information about your company. No need to fill
out your information here, which will be needed in part 6.

f*l2011-01-25 08:01

6 楼

LOL.

【在 x*****a 的大作中提到】

: 以前同学读课文，其中有一句：拿出芭蕉扇扇扇。本来停顿应该是拿出芭蕉扇，扇扇。
: 那同学直接读成：拿出芭蕉，扇扇扇！

c*e2011-01-25 08:01

7 楼

Could you give more information for " in-place swap the i to (i-1)-th of the
array." ? Thanks

J*y2011-01-25 08:01

8 楼

THANKS

P*r2011-01-25 08:01

9 楼

Just create an array A[100] initialized to 0, and iterate the numbers, say i
, set A[i]=1. Then the index j of the array with A[j]==0 is the number
missing.

G*o2011-01-25 08:01

10 楼

this solution requires O(n) space, not constant

i

【在 P******r 的大作中提到】

: Just create an array A[100] initialized to 0, and iterate the numbers, say i
: , set A[i]=1. Then the index j of the array with A[j]==0 is the number
: missing.

s*y2011-01-25 08:01

11 楼

Just 0 ~ 100 ? So it only occupy 6 bits.
Could you use the highest 6 bits to be your hash bit?
It maybe more easier than swap then.

【在 G*********o 的大作中提到】

: this solution requires O(n) space, not constant
:
: i

r*l2011-01-25 08:01

12 楼

But the space complexity would be dependent on N

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

: Just 0 ~ 100 ? So it only occupy 6 bits.
: Could you use the highest 6 bits to be your hash bit?
: It maybe more easier than swap then.

r*l2011-01-25 08:01

13 楼

I got the idea, thanks!

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

: Discussed in the last month. in-place swap the i to (i-1)-th of the array.
:
: array
: constant

s*y2011-01-25 08:01

14 楼

why you need space?
you set the bits of the array in place.

【在 r****l 的大作中提到】

:
: I got the idea, thanks!

r*l2011-01-25 08:01

15 楼

you mean use one of the element space as a bitmap?
I think it'll work, and we can also reset that element after find out all
missing numbers, thus the array will
remain unchanged.
Cool.

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

: why you need space?
: you set the bits of the array in place.

s*y2011-01-25 08:01

16 楼

yes.

【在 r****l 的大作中提到】

:
: you mean use one of the element space as a bitmap?
: I think it'll work, and we can also reset that element after find out all
: missing numbers, thus the array will
: remain unchanged.
: Cool.

B*t2011-01-25 08:01

17 楼

这样只能找到1－sizeof array之间的missing，不是1－100之间的

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

: Discussed in the last month. in-place swap the i to (i-1)-th of the array.
:
: array
: constant

g*s2011-01-25 08:01

18 楼

http://www.mitbbs.com/article_t1/JobHunting/31827743_0_3.html
47 Lou

the

【在 c******e 的大作中提到】

: Could you give more information for " in-place swap the i to (i-1)-th of the
: array." ? Thanks

g*s2011-01-25 08:01

19 楼

can we assume k<=n/2?
then use this method again.

【在 B*******t 的大作中提到】

: 这样只能找到1－sizeof array之间的missing，不是1－100之间的

B*t2011-01-25 08:01

20 楼

then how to do inplace? You lose data in the first pass.

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

: can we assume k<=n/2?
: then use this method again.

g*s2011-01-25 08:01

21 楼

m = length of the array
first time, skip all numbers > m
inplance swap, scan find all mising number beteen 1 and m.
then, only check all numbers > m,
inplance to swap these number to (i-1)-m th
scan find all missing number between m+1 and n

【在 B*******t 的大作中提到】

: then how to do inplace? You lose data in the first pass.

g*e2011-01-25 08:01

22 楼

学习

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

: m = length of the array
: first time, skip all numbers > m
: inplance swap, scan find all mising number beteen 1 and m.
: then, only check all numbers > m,
: inplance to swap these number to (i-1)-m th
: scan find all missing number between m+1 and n

B*t2011-01-25 08:01

23 楼

多谢，学习一下

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

g*s2011-01-25 08:01

24 楼

这是哪家？

array
constant

【在 r****l 的大作中提到】

f*42011-01-25 08:01

25 楼

这个题目，要是我用 k个space，算是constant space么？

k*p2011-01-25 08:01

26 楼

感觉有点小小的漏洞，如果m很小，比如20，那你得分5段筛选吧。

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

r*r2011-01-25 08:01

27 楼

如果是排序的，就简单吧。里面那个打印的 for loop 不算，就是 O(n). 便于测试，
假设从 10 个中找 k missing number.
Input: int[] a = {4, 5, 7, 10};
int k = 6;
Output: 1 2 3 6 8 9
public static void findMissing(int[] a, int k){
int l =1;
int i =0;
while(i<10-k){
int diff = a[i]-l;
if(diff == 0){
i++;
l++;
}else{
int big = a[i];
for(int j=l; jSystem.out.print(" " + j);
l++;
}

}
}
if( l <= 10 ){
while( l <= 10){
System.out.println(" " + l);
l++;
}
}
}
如果是 unsorted，就不行了

r*r2011-01-25 08:01

28 楼

对了，看见题目里面说 unsorted，not work.
sorry.

【在 r******r 的大作中提到】

: 如果是排序的，就简单吧。里面那个打印的 for loop 不算，就是 O(n). 便于测试，
: 假设从 10 个中找 k missing number.
: Input: int[] a = {4, 5, 7, 10};
: int k = 6;
: Output: 1 2 3 6 8 9
: public static void findMissing(int[] a, int k){
: int l =1;
: int i =0;
: while(i<10-k){
: int diff = a[i]-l;

g*s2011-01-25 08:01

29 楼

that's true.
That's why I said: assume m>= n/2 based on the word 'missing'.

【在 k*******p 的大作中提到】

: 感觉有点小小的漏洞，如果m很小，比如20，那你得分5段筛选吧。

q*92011-01-25 08:01

30 楼

那还叫missing么，那应该是在数组里的叫missing了

【在 k*******p 的大作中提到】

: 感觉有点小小的漏洞，如果m很小，比如20，那你得分5段筛选吧。

a*m2011-01-25 08:01

31 楼

用bool flags[100]算不算constant space?

constant

【在 r****l 的大作中提到】

h*n2011-01-25 08:01

32 楼

先在数组结尾补k个-1
for i in range(len(list)):
while list[i] != i:
if(list[i]==-1):
break
temp = list[i]
list[i] = list[list[i]]
list[temp] = temp
每次至少把一个数放到自己的位置上
最后扫描一遍，-1都在missing number的位置上

【在 a********m 的大作中提到】

: 用bool flags[100]算不算constant space?
:
: constant

s*n2011-01-25 08:01

33 楼

算，不然为什么说100-k, 而不是简单的n-k.

【在 a********m 的大作中提到】

: 用bool flags[100]算不算constant space?
:
: constant

a*m2011-01-25 08:01

34 楼

那用标记数组不就可以了？

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

: 算，不然为什么说100-k, 而不是简单的n-k.

P*c2011-01-25 08:01

35 楼

数组结尾可以随便补吗？万一定义的数组长度就是100-k呢。

【在 h*********n 的大作中提到】

: 先在数组结尾补k个-1
: for i in range(len(list)):
: while list[i] != i:
: if(list[i]==-1):
: break
: temp = list[i]
: list[i] = list[list[i]]
: list[temp] = temp
: 每次至少把一个数放到自己的位置上
: 最后扫描一遍，-1都在missing number的位置上

s*n2011-01-25 08:01

36 楼

两个int64或者long long就搞定了。

【在 a********m 的大作中提到】

: 那用标记数组不就可以了？