r****l
发帖数: 28 | 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? |
g***s
发帖数: 3811 | 2 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?
|
c******e
发帖数: 73 | 3 Could you give more information for " in-place swap the i to (i-1)-th of the
array." ? Thanks |
P******r
发帖数: 85 | 4 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*********o
发帖数: 2045 | 5 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*****y
发帖数: 897 | 6 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****l
发帖数: 28 | 7
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****l
发帖数: 28 | 8
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*****y
发帖数: 897 | 9 why you need space?
you set the bits of the array in place.
【在 r****l 的大作中提到】
:
: I got the idea, thanks!
|
r****l
发帖数: 28 | 10
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*****y
发帖数: 897 | 11 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*******t
发帖数: 403 | 12 这样只能找到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***s
发帖数: 3811 | 13 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***s
发帖数: 3811 | 14 can we assume k<=n/2?
then use this method again.
【在 B*******t 的大作中提到】
: 这样只能找到1－sizeof array之间的missing，不是1－100之间的
|
B*******t
发帖数: 403 | 15 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***s
发帖数: 3811 | 16 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**e
发帖数: 6127 | 17 学习
【在 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*******t
发帖数: 403 | 18 多谢，学习一下
【在 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
|
g*********s
发帖数: 1782 | 19 这是哪家？
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?
|
f****4
发帖数: 1359 | 20 这个题目，要是我用 k个space，算是constant space么？ |
|
|
k*******p
发帖数: 219 | 21 感觉有点小小的漏洞，如果m很小，比如20，那你得分5段筛选吧。
【在 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
|
r******r
发帖数: 700 | 22 如果是排序的，就简单吧。里面那个打印的 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; j
System.out.print(" " + j);
l++;
}
}
}
if( l <= 10 ){
while( l <= 10){
System.out.println(" " + l);
l++;
}
}
}
如果是 unsorted，就不行了 |
r******r
发帖数: 700 | 23 对了，看见题目里面说 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***s
发帖数: 3811 | 24 that's true.
That's why I said: assume m>= n/2 based on the word 'missing'.
【在 k*******p 的大作中提到】
: 感觉有点小小的漏洞，如果m很小，比如20，那你得分5段筛选吧。
|
q*****9
发帖数: 85 | 25 那还叫missing么，那应该是在数组里的叫missing了
【在 k*******p 的大作中提到】
: 感觉有点小小的漏洞，如果m很小，比如20，那你得分5段筛选吧。
|
a********m
发帖数: 15480 | 26 用bool flags[100]算不算constant space?
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?
|
h*********n
发帖数: 11319 | 27 先在数组结尾补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*****n
发帖数: 5488 | 28 算，不然为什么说100-k, 而不是简单的n-k.
【在 a********m 的大作中提到】
: 用bool flags[100]算不算constant space?
:
: constant
|
a********m
发帖数: 15480 | 29 那用标记数组不就可以了？
【在 s*****n 的大作中提到】
: 算，不然为什么说100-k, 而不是简单的n-k.
|
P**********c
发帖数: 3417 | 30 数组结尾可以随便补吗？万一定义的数组长度就是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*****n
发帖数: 5488 | 31 两个int64或者long long就搞定了。
【在 a********m 的大作中提到】
: 那用标记数组不就可以了？
|
