由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问个题:大小N的数组有 N-k个不同的数, 范围0-N, 找missing的k个
相关主题
昨天面试的一道题,find k missing numbers为啥这个swap不可以?
分享一道电面题,兼下午Onsite攒人品求祝福荷兰国旗问题的扩展
问个题问一道题
问个题:3n-2数组里面找到只出现一次的数?再发几个面试题
问个题,bt中找最大的bsta1b2c3d4 变abcd1234
一个算法题讨论一道老题:分离数组中的正负数 (转载)
问一题:merge两个有序数组BB家面经
这道题太神奇了,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),刚做了一道有些怪异的题
相关话题的讨论汇总
话题: int话题: arr话题: hit话题: missing话题: 数组
进入JobHunting版参与讨论
1 (共1页)
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;

相关主题
一个算法题为啥这个swap不可以?
问一题:merge两个有序数组荷兰国旗问题的扩展
这道题太神奇了,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),问一道题
进入JobHunting版参与讨论
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;

1 (共1页)
进入JobHunting版参与讨论
相关主题
刚做了一道有些怪异的题问个题,bt中找最大的bst
求问一道数组shuffle的问题一个算法题
被基础题搞挂了问一题:merge两个有序数组
问一道leetcode题:recover BST这道题太神奇了,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),
昨天面试的一道题,find k missing numbers为啥这个swap不可以?
分享一道电面题,兼下午Onsite攒人品求祝福荷兰国旗问题的扩展
问个题问一道题
问个题:3n-2数组里面找到只出现一次的数?再发几个面试题
相关话题的讨论汇总
话题: int话题: arr话题: hit话题: missing话题: 数组