w***y 发帖数: 6251 | 1 要求用O(1) space
我只知道大概的思路是, 将a[i]放到a[a[i]-1]的位子上, 但是不知道具体怎么做的
, 原来a[a[i]-1]的那个数怎么处理? |
h**********l 发帖数: 6342 | 2 swap,不是直接覆盖
【在 w***y 的大作中提到】 : 要求用O(1) space : 我只知道大概的思路是, 将a[i]放到a[a[i]-1]的位子上, 但是不知道具体怎么做的 : , 原来a[a[i]-1]的那个数怎么处理?
|
w***y 发帖数: 6251 | 3 需要先排序么? 想不通swap为什么就可以了
完蛋了, 最近几天脑子很糊涂。。。。。。
【在 h**********l 的大作中提到】 : swap,不是直接覆盖
|
y********g 发帖数: 8 | 4 a[a[i]-1]放到a[a[a[i]-1]-1],以此类推 |
w***y 发帖数: 6251 | 5 ok, 就是对每一个a[i]都这么一路推下去直到出界或者那个位子的数已经放对了
【在 y********g 的大作中提到】 : a[a[i]-1]放到a[a[a[i]-1]-1],以此类推
|
B***n 发帖数: 84 | 6 时间复杂度呢?
O(n2)?
【在 w***y 的大作中提到】 : ok, 就是对每一个a[i]都这么一路推下去直到出界或者那个位子的数已经放对了
|
l*********8 发帖数: 4642 | 7 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)?
|
y****n 发帖数: 743 | 8 这个算法有如下问题:
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]]);
|
y****n 发帖数: 743 | 9 这个应该可以,大家挑挑毛病
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;
} |
S****h 发帖数: 115 | 10 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;
|
|
|
S****h 发帖数: 115 | 11 也贴一个自己的练手,请赐教
// 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]的那个数怎么处理?
|
p*****2 发帖数: 21240 | 12 没想到这里还提到我了。这题我没做过。现在头疼。一会儿过来学习一下。 |
y****n 发帖数: 743 | 13 是用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代码浅显易懂,霸气威武。建议参考
|
S****h 发帖数: 115 | 14 不好意思,发现是我copy你的代码该的时候修改错地方了。
赞,解法~
【在 y****n 的大作中提到】 : 是用C#写的,下午忙着去开会,没写思路。 : 1. 如果某数字m出现,则在原数组的第m个元素作标记。 : 标记的方式:该元素的值减去数组总长度(count)。这样被标记过的元素一定是负数 : ,并且可以恢复其原值(+count即可)。 : 2. 时间优化,能用一重循环则不用二重循环。 : 3. 运算结束时,恢复原数组全部数据,保持原顺序。 : 4. 同时考虑到算有运算不会有整数溢出情况。 : 5. 正常项目当然不会这样写代码,都是那个空间O(1)要求的。 : 我运转了一下test case{ 1, 1},我的代码没有数组越界呀? : 在正式的面试中,一重循环O(n),还是比二重循环O(n^2)有明显优势的。
|
k**d 发帖数: 431 | 15 O(1) space的意思是说可以使用额外的constant空间吧?
【在 w***y 的大作中提到】 : 要求用O(1) space : 我只知道大概的思路是, 将a[i]放到a[a[i]-1]的位子上, 但是不知道具体怎么做的 : , 原来a[a[i]-1]的那个数怎么处理?
|
p*****2 发帖数: 21240 | 16 在看这题,首先
a[a[i]-1]
如果a[i]==0的话,不就有问题了吗? |
p*****2 发帖数: 21240 | 17
看起来还是很牛的code,考虑挺周全
【在 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;
|