顶着锅盖真诚提个建议：大家少用Bless吧# Immigration - 落地生根
w*y
1 楼
要求用O(1) space
我只知道大概的思路是， 将a[i]放到a[a[i]-1]的位子上， 但是不知道具体怎么做的
， 原来a[a[i]-1]的那个数怎么处理？
我只知道大概的思路是， 将a[i]放到a[a[i]-1]的位子上， 但是不知道具体怎么做的
， 原来a[a[i]-1]的那个数怎么处理？
A*o
2 楼
一个帖子20多个回复，想看点有用信息，进去一看全是bless。
我也跟大家心情一样，但是bless真的没用的。
谢谢
我也跟大家心情一样，但是bless真的没用的。
谢谢
h*l
3 楼
swap，不是直接覆盖
【在 w***y 的大作中提到】
: 要求用O(1) space
: 我只知道大概的思路是， 将a[i]放到a[a[i]-1]的位子上， 但是不知道具体怎么做的
: ， 原来a[a[i]-1]的那个数怎么处理？
【在 w***y 的大作中提到】
: 要求用O(1) space
: 我只知道大概的思路是， 将a[i]放到a[a[i]-1]的位子上， 但是不知道具体怎么做的
: ， 原来a[a[i]-1]的那个数怎么处理？
c*g
4 楼
hao
【在 A**o 的大作中提到】
: 一个帖子20多个回复，想看点有用信息，进去一看全是bless。
: 我也跟大家心情一样，但是bless真的没用的。
: 谢谢
【在 A**o 的大作中提到】
: 一个帖子20多个回复，想看点有用信息，进去一看全是bless。
: 我也跟大家心情一样，但是bless真的没用的。
: 谢谢
w*y
5 楼
需要先排序么？ 想不通swap为什么就可以了
完蛋了， 最近几天脑子很糊涂。。。。。。
【在 h**********l 的大作中提到】
: swap，不是直接覆盖
完蛋了， 最近几天脑子很糊涂。。。。。。
【在 h**********l 的大作中提到】
: swap，不是直接覆盖
e*r
6 楼
真不真诚，上个本人pp才知道。
有没有用， 单个人鉴定那不算。
求bless，找的是个心安，
送bless，攒的是个rp。
板上有用信息多了，找不到的，建议提高自身考古水平，
若是挖错坟了，又怎能怪得了他人？？
有没有用， 单个人鉴定那不算。
求bless，找的是个心安，
送bless，攒的是个rp。
板上有用信息多了，找不到的，建议提高自身考古水平，
若是挖错坟了，又怎能怪得了他人？？
y*g
7 楼
a[a[i]-1]放到a[a[a[i]-1]-1]，以此类推
c*g
8 楼
好
【在 e******r 的大作中提到】
: 真不真诚，上个本人pp才知道。
: 有没有用， 单个人鉴定那不算。
: 求bless，找的是个心安，
: 送bless，攒的是个rp。
: 板上有用信息多了，找不到的，建议提高自身考古水平，
: 若是挖错坟了，又怎能怪得了他人？？
【在 e******r 的大作中提到】
: 真不真诚，上个本人pp才知道。
: 有没有用， 单个人鉴定那不算。
: 求bless，找的是个心安，
: 送bless，攒的是个rp。
: 板上有用信息多了，找不到的，建议提高自身考古水平，
: 若是挖错坟了，又怎能怪得了他人？？
w*y
9 楼
ok, 就是对每一个a[i]都这么一路推下去直到出界或者那个位子的数已经放对了
【在 y********g 的大作中提到】
: a[a[i]-1]放到a[a[a[i]-1]-1]，以此类推
【在 y********g 的大作中提到】
: a[a[i]-1]放到a[a[a[i]-1]-1]，以此类推
L*r
10 楼
bless you...
B*n
11 楼
时间复杂度呢？
O(n2)?
【在 w***y 的大作中提到】
: ok, 就是对每一个a[i]都这么一路推下去直到出界或者那个位子的数已经放对了
O(n2)?
【在 w***y 的大作中提到】
: ok, 就是对每一个a[i]都这么一路推下去直到出界或者那个位子的数已经放对了
T*y
12 楼
Zan!
【在 e******r 的大作中提到】
: 真不真诚，上个本人pp才知道。
: 有没有用， 单个人鉴定那不算。
: 求bless，找的是个心安，
: 送bless，攒的是个rp。
: 板上有用信息多了，找不到的，建议提高自身考古水平，
: 若是挖错坟了，又怎能怪得了他人？？
【在 e******r 的大作中提到】
: 真不真诚，上个本人pp才知道。
: 有没有用， 单个人鉴定那不算。
: 求bless，找的是个心安，
: 送bless，攒的是个rp。
: 板上有用信息多了，找不到的，建议提高自身考古水平，
: 若是挖错坟了，又怎能怪得了他人？？
l*8
13 楼
O(N)
// 大小N的数组有 N-k个不同的数， 范围 0-N-1， 找miss
// 注意：跟楼主题目不同，我假设数字范围从0 -- N-1
vector FindMissingNumbers(vector & a)
{
vector missing;
for (int i=0; i
while (a[i]!=a[a[i]])
swap(a[i], a[a[i]]);
if (a[i] != i)
missing.push_back(i);
}
return missing;
}
【在 B***n 的大作中提到】
: 时间复杂度呢？
: O(n2)?
// 大小N的数组有 N-k个不同的数， 范围 0-N-1， 找miss
// 注意：跟楼主题目不同，我假设数字范围从0 -- N-1
vector
{
vector
for (int i=0; i
while (a[i]!=a[a[i]])
swap(a[i], a[a[i]]);
if (a[i] != i)
missing.push_back(i);
}
return missing;
}
【在 B***n 的大作中提到】
: 时间复杂度呢？
: O(n2)?
L*i
14 楼
bless才有人情味儿啊
y*n
15 楼
这个算法有如下问题：
1. 某些时候会返回错误结果
比如输入：{ 1, 1, 0 }，结果中0也别认为是missing。
2. 两重循环，算法的复杂度是O(n^2)
3. 执行结束后，原数组的内容（循序）被更改。
【在 l*********8 的大作中提到】
: O(N)
: // 大小N的数组有 N-k个不同的数， 范围 0-N-1， 找miss
: // 注意：跟楼主题目不同，我假设数字范围从0 -- N-1
: vector FindMissingNumbers(vector & a)
: {
: vector missing;
: for (int i=0; i
: while (a[i]!=a[a[i]])
: swap(a[i], a[a[i]]);
1. 某些时候会返回错误结果
比如输入：{ 1, 1, 0 }，结果中0也别认为是missing。
2. 两重循环，算法的复杂度是O(n^2)
3. 执行结束后，原数组的内容（循序）被更改。
【在 l*********8 的大作中提到】
: O(N)
: // 大小N的数组有 N-k个不同的数， 范围 0-N-1， 找miss
: // 注意：跟楼主题目不同，我假设数字范围从0 -- N-1
: vector
: {
: vector
: for (int i=0; i
: while (a[i]!=a[a[i]])
: swap(a[i], a[a[i]]);
x*w
16 楼
按你的说法，以后大家就不要求bless就好了！
y*n
17 楼
这个应该可以，大家挑挑毛病
private static List FindMissing(List input)
{
List missing = new List();
int count = input.Count;
for (int i = 0; i < count; i++)
{
int value = input[i];
if (value < 0)
value += count;
if (input[value] >= 0)
input[value] -= count;
}
for (int i = 0; i < input.Count; i++)
{
if (input[i] >= 0)
missing.Add(i);
else
input[i] += count;
}
return missing;
}
private static List
{
List
int count = input.Count;
for (int i = 0; i < count; i++)
{
int value = input[i];
if (value < 0)
value += count;
if (input[value] >= 0)
input[value] -= count;
}
for (int i = 0; i < input.Count; i++)
{
if (input[i] >= 0)
missing.Add(i);
else
input[i] += count;
}
return missing;
}
s*o
18 楼
bless!
S*h
19 楼
yishan, 这是用C#写的么？
提点建议：
1.代码会有抛数组越界的情况，test case{ 1, 1};
2.你的代码可以读我觉得真的不强//或者是我没有抓到你的思路，还请加些comments
peking2写dp代码浅显易懂，霸气威武。建议参考
【在 y****n 的大作中提到】
: 这个应该可以，大家挑挑毛病
: private static List FindMissing(List input)
: {
: List missing = new List();
: int count = input.Count;
: for (int i = 0; i < count; i++)
: {
: int value = input[i];
: if (value < 0)
: value += count;
提点建议：
1.代码会有抛数组越界的情况，test case{ 1, 1};
2.你的代码可以读我觉得真的不强//或者是我没有抓到你的思路，还请加些comments
peking2写dp代码浅显易懂，霸气威武。建议参考
【在 y****n 的大作中提到】
: 这个应该可以，大家挑挑毛病
: private static List
: {
: List
: int count = input.Count;
: for (int i = 0; i < count; i++)
: {
: int value = input[i];
: if (value < 0)
: value += count;
k*w
20 楼
Bless帖没啥，不像话的是送出去Bless后竟然
没得到包子
没得到包子
S*h
21 楼
也贴一个自己的练手，请赐教
// assume all values are between 0 ~ N-1
public static void findAbsentNumber(int[] arr) {
if (arr == null || arr.length == 0)
return;
// mark all a[i] as -1 if i presents in the array
for (int i = 0; i < arr.length; i++) {
int hit = arr[i];
while (hit != -1 && arr[hit] != -1) {
int temp = arr[hit];
arr[hit] = -1; // marked presence
hit = temp;
}
}
// print out all value without presence
for (int i = 0; i < arr.length; i++) {
if (arr[i] != -1)
System.out.printf(" %1$d", i);
}
}
【在 w***y 的大作中提到】
: 要求用O(1) space
: 我只知道大概的思路是， 将a[i]放到a[a[i]-1]的位子上， 但是不知道具体怎么做的
: ， 原来a[a[i]-1]的那个数怎么处理？
// assume all values are between 0 ~ N-1
public static void findAbsentNumber(int[] arr) {
if (arr == null || arr.length == 0)
return;
// mark all a[i] as -1 if i presents in the array
for (int i = 0; i < arr.length; i++) {
int hit = arr[i];
while (hit != -1 && arr[hit] != -1) {
int temp = arr[hit];
arr[hit] = -1; // marked presence
hit = temp;
}
}
// print out all value without presence
for (int i = 0; i < arr.length; i++) {
if (arr[i] != -1)
System.out.printf(" %1$d", i);
}
}
【在 w***y 的大作中提到】
: 要求用O(1) space
: 我只知道大概的思路是， 将a[i]放到a[a[i]-1]的位子上， 但是不知道具体怎么做的
: ， 原来a[a[i]-1]的那个数怎么处理？
e*r
22 楼
哈哈~有趣
就是,他们太不像话了,倒是兄台的头像很像画
【在 k**w 的大作中提到】
: Bless帖没啥，不像话的是送出去Bless后竟然
: 没得到包子
就是,他们太不像话了,倒是兄台的头像很像画
【在 k**w 的大作中提到】
: Bless帖没啥，不像话的是送出去Bless后竟然
: 没得到包子
p*2
23 楼
没想到这里还提到我了。这题我没做过。现在头疼。一会儿过来学习一下。
c*g
24 楼
我本想再问的，算了。我忍住了
【在 k**w 的大作中提到】
: Bless帖没啥，不像话的是送出去Bless后竟然
: 没得到包子
【在 k**w 的大作中提到】
: Bless帖没啥，不像话的是送出去Bless后竟然
: 没得到包子
y*n
25 楼
是用C#写的，下午忙着去开会，没写思路。
1. 如果某数字m出现，则在原数组的第m个元素作标记。
标记的方式：该元素的值减去数组总长度（count）。这样被标记过的元素一定是负数
，并且可以恢复其原值(+count即可)。
2. 时间优化，能用一重循环则不用二重循环。
3. 运算结束时，恢复原数组全部数据，保持原顺序。
4. 同时考虑到算有运算不会有整数溢出情况。
5. 正常项目当然不会这样写代码，都是那个空间O(1)要求的。
我运转了一下test case{ 1, 1}，我的代码没有数组越界呀？
在正式的面试中，一重循环O(n)，还是比二重循环O(n^2)有明显优势的。
【在 S****h 的大作中提到】
: yishan, 这是用C#写的么？
: 提点建议：
: 1.代码会有抛数组越界的情况，test case{ 1, 1};
: 2.你的代码可以读我觉得真的不强//或者是我没有抓到你的思路，还请加些comments
: peking2写dp代码浅显易懂，霸气威武。建议参考
1. 如果某数字m出现，则在原数组的第m个元素作标记。
标记的方式：该元素的值减去数组总长度（count）。这样被标记过的元素一定是负数
，并且可以恢复其原值(+count即可)。
2. 时间优化，能用一重循环则不用二重循环。
3. 运算结束时，恢复原数组全部数据，保持原顺序。
4. 同时考虑到算有运算不会有整数溢出情况。
5. 正常项目当然不会这样写代码，都是那个空间O(1)要求的。
我运转了一下test case{ 1, 1}，我的代码没有数组越界呀？
在正式的面试中，一重循环O(n)，还是比二重循环O(n^2)有明显优势的。
【在 S****h 的大作中提到】
: yishan, 这是用C#写的么？
: 提点建议：
: 1.代码会有抛数组越界的情况，test case{ 1, 1};
: 2.你的代码可以读我觉得真的不强//或者是我没有抓到你的思路，还请加些comments
: peking2写dp代码浅显易懂，霸气威武。建议参考
e*r
26 楼
7,你那弱智儿童问题不就是说他那头像是谁嘛.
这都不知道呀,那是注明的'蒙娜憨豆中风图'
【在 c******g 的大作中提到】
: 我本想再问的，算了。我忍住了
这都不知道呀,那是注明的'蒙娜憨豆中风图'
【在 c******g 的大作中提到】
: 我本想再问的，算了。我忍住了
S*h
27 楼
不好意思，发现是我copy你的代码该的时候修改错地方了。
赞，解法~
【在 y****n 的大作中提到】
: 是用C#写的，下午忙着去开会，没写思路。
: 1. 如果某数字m出现，则在原数组的第m个元素作标记。
: 标记的方式：该元素的值减去数组总长度（count）。这样被标记过的元素一定是负数
: ，并且可以恢复其原值(+count即可)。
: 2. 时间优化，能用一重循环则不用二重循环。
: 3. 运算结束时，恢复原数组全部数据，保持原顺序。
: 4. 同时考虑到算有运算不会有整数溢出情况。
: 5. 正常项目当然不会这样写代码，都是那个空间O(1)要求的。
: 我运转了一下test case{ 1, 1}，我的代码没有数组越界呀？
: 在正式的面试中，一重循环O(n)，还是比二重循环O(n^2)有明显优势的。
赞，解法~
【在 y****n 的大作中提到】
: 是用C#写的，下午忙着去开会，没写思路。
: 1. 如果某数字m出现，则在原数组的第m个元素作标记。
: 标记的方式：该元素的值减去数组总长度（count）。这样被标记过的元素一定是负数
: ，并且可以恢复其原值(+count即可)。
: 2. 时间优化，能用一重循环则不用二重循环。
: 3. 运算结束时，恢复原数组全部数据，保持原顺序。
: 4. 同时考虑到算有运算不会有整数溢出情况。
: 5. 正常项目当然不会这样写代码，都是那个空间O(1)要求的。
: 我运转了一下test case{ 1, 1}，我的代码没有数组越界呀？
: 在正式的面试中，一重循环O(n)，还是比二重循环O(n^2)有明显优势的。
b*r
28 楼
bless.
k*d
29 楼
O(1) space的意思是说可以使用额外的constant空间吧？
【在 w***y 的大作中提到】
: 要求用O(1) space
: 我只知道大概的思路是， 将a[i]放到a[a[i]-1]的位子上， 但是不知道具体怎么做的
: ， 原来a[a[i]-1]的那个数怎么处理？
【在 w***y 的大作中提到】
: 要求用O(1) space
: 我只知道大概的思路是， 将a[i]放到a[a[i]-1]的位子上， 但是不知道具体怎么做的
: ， 原来a[a[i]-1]的那个数怎么处理？
c*g
30 楼
你也不给我六点脸面
我也老大不小的一个男人了
怎么也不是弱智儿童了
【在 e******r 的大作中提到】
: 7,你那弱智儿童问题不就是说他那头像是谁嘛.
: 这都不知道呀,那是注明的'蒙娜憨豆中风图'
我也老大不小的一个男人了
怎么也不是弱智儿童了
【在 e******r 的大作中提到】
: 7,你那弱智儿童问题不就是说他那头像是谁嘛.
: 这都不知道呀,那是注明的'蒙娜憨豆中风图'
p*2
31 楼
在看这题，首先
a[a[i]-1]
如果a[i]==0的话，不就有问题了吗？
a[a[i]-1]
如果a[i]==0的话，不就有问题了吗？
e*r
32 楼
我错了。。。bless～
【在 c******g 的大作中提到】
: 你也不给我六点脸面
: 我也老大不小的一个男人了
: 怎么也不是弱智儿童了
【在 c******g 的大作中提到】
: 你也不给我六点脸面
: 我也老大不小的一个男人了
: 怎么也不是弱智儿童了
p*2
33 楼
看起来还是很牛的code，考虑挺周全
【在 y****n 的大作中提到】
: 这个应该可以，大家挑挑毛病
: private static List
: {
: List
: int count = input.Count;
: for (int i = 0; i < count; i++)
: {
: int value = input[i];
: if (value < 0)
: value += count;
c*g
34 楼
我把我图像也换了。O(∩_∩)O哈哈~
【在 e******r 的大作中提到】
: 我错了。。。bless～
【在 e******r 的大作中提到】
: 我错了。。。bless～
S*g
35 楼
bless!!
k*w
36 楼
多谢捧场：）
【在 c******g 的大作中提到】
: 我把我图像也换了。O(∩_∩)O哈哈~
【在 c******g 的大作中提到】
: 我把我图像也换了。O(∩_∩)O哈哈~
s*y
37 楼
呵呵你太贫了！
【在 e******r 的大作中提到】
: 哈哈~有趣
: 就是,他们太不像话了,倒是兄台的头像很像画
【在 e******r 的大作中提到】
: 哈哈~有趣
: 就是,他们太不像话了,倒是兄台的头像很像画
e*r
38 楼
*(∩_∩)*
【在 s*******y 的大作中提到】
: 呵呵你太贫了！
【在 s*******y 的大作中提到】
: 呵呵你太贫了！
h*n
39 楼
bless
相关阅读
485 pending 期间的工作可以是 part time 的吗？关于网页转PDF的问题FP一个月了还没有Update正常吗？ (转载)NSC greened ? 01/07/2013 RD真诚求建议，关于搬家和PP请问ESI给出引用在10%可以算在small percentage里吗？律师求推荐绿卡没批 影响下次申请吗485 questionEB1a 没有Initial Review直接RFE?结婚公证 问题请教求下载文章征文）新的一年EB1B，60篇引用可以单独claim citation吗?律师不给看petition letter, 这个正常吗？毕业到工作之间有四个月gap要怎么写?填140疑问要办I１４０?什么样的才是好律师？请教I-765 第16项对于副申请人F1 应该如何填写（主申请人为H1B)