R***i
发帖数: 78 | 1 公司名就不说了
题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
我给了2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of
integers， time O(n), space O(n)。 但面试的人告诉我都不是最优解，有time O(n)
, constant space的解。。。现在都没想明白，大家集思广益吧 |
g***s
发帖数: 3811 | 2 没有重复的话，很容易。
1. 先找到最小的正数t
2. 对每一个数字，如果值k-t是0－n-1，就替换到位置k-t上去
3. 遍力找第一个不match的 |
g***s
发帖数: 3811 | 3 有重复这方法也有效。重复的元素skip就可以
★ Sent from iPhone App: iReader Mitbbs 6.0 - iPhone Lite |
m****v
发帖数: 84 | 4
const space?
【在 g***s 的大作中提到】
: 有重复这方法也有效。重复的元素skip就可以
: ★ Sent from iPhone App: iReader Mitbbs 6.0 - iPhone Lite
|
g***s
发帖数: 3811 | |
f***g
发帖数: 214 | 6 0.02:
如果可以改变原数组的话，用Swap算法应该可以吧。
就是把数字放到和自己下标对应的那个位置。
然后从位置1开始扫描找到
data[i] != i;
return i; |
m****v
发帖数: 84 | 7
yes, good idea
【在 g***s 的大作中提到】
: 只用原来的空间
|
m****v
发帖数: 84 | 8
well, but actually the space you will use is not 'constant'
if the spec says 'no extra space', it is fine
is it?
【在 g***s 的大作中提到】
: 只用原来的空间
|
s*******n
发帖数: 344 | 9 # Pass 1, move every value to the position of its value
for cursor in range(N):
target = array[cursor]
while target < N and target != array[target]:
new_target = array[target]
array[target] = target
target = new_target
# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
if array[cursor] != cursor:
return cursor
return N
http://stackoverflow.com/questions/1586858/find-the-smallest-in |
s*****y
发帖数: 897 | 10 Drop the element if < 0 ?
【在 s*******n 的大作中提到】
: # Pass 1, move every value to the position of its value
: for cursor in range(N):
: target = array[cursor]
: while target < N and target != array[target]:
: new_target = array[target]
: array[target] = target
: target = new_target
: # Pass 2, find first location where the index doesn't match the value
: for cursor in range(N):
: if array[cursor] != cursor:
|
|
|
l********y
发帖数: 1327 | |
s*****y
发帖数: 897 | 12 So the method is kind of like
give a array with number range from 0 - 100, one number is duplicate. Find
the duplicate. Right?
【在 s*******n 的大作中提到】
: # Pass 1, move every value to the position of its value
: for cursor in range(N):
: target = array[cursor]
: while target < N and target != array[target]:
: new_target = array[target]
: array[target] = target
: target = new_target
: # Pass 2, find first location where the index doesn't match the value
: for cursor in range(N):
: if array[cursor] != cursor:
|
i**********e
发帖数: 1145 | 13 基于你的方法再做一些优化.
没必要找最小的正数（因为是大于0，如果大于k的话就要）.
把每个数字 swap 到它的正确 index 去，如果是小于 0 或者大于 n-1 就跳过，直到
没的swap为止.
For example,
[3,4,-1,1]
-> [1,4,-1,3] (3 与 1 对换）
-> [4,1,-1,3] (1 与 4 对换）
-> [x,1,-1,3] (跳过 4）
-> [x,1,-1,3] (跳过 1，因为 1 已经在对的位置）
-> [x,1,x,3] （跳过-1）
-> [x,1,x,3] （跳过3)
那么再扫描一遍就可以得知第一个大于0而不再数组里的数字是2.
这个思路的重点就是：
1) 在一个 n size 数组里的 range 如果不是 0 - n-1，那么第一个大于0而不在数组
里的数字必定是 1 - n-1 (inclusive).
2) 反之，在一个 n size 数组里的 range 如果是 0 - n-1，那么第一个大于0而不在
数组里的数字必定是 n.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g***s 的大作中提到】
: 没有重复的话，很容易。
: 1. 先找到最小的正数t
: 2. 对每一个数字，如果值k-t是0－n-1，就替换到位置k-t上去
: 3. 遍力找第一个不match的
|
s*****y
发帖数: 897 | 14 Is it possible the input array like this?
3 4 -1 1000
【在 i**********e 的大作中提到】
: 基于你的方法再做一些优化.
: 没必要找最小的正数（因为是大于0，如果大于k的话就要）.
: 把每个数字 swap 到它的正确 index 去，如果是小于 0 或者大于 n-1 就跳过，直到
: 没的swap为止.
: For example,
: [3,4,-1,1]
: -> [1,4,-1,3] (3 与 1 对换）
: -> [4,1,-1,3] (1 与 4 对换）
: -> [x,1,-1,3] (跳过 4）
: -> [x,1,-1,3] (跳过 1，因为 1 已经在对的位置）
|
i**********e
发帖数: 1145 | 15 sure.
After swapping all elements. (-1, 4 and 1000 will be ignored), The final
array should be:
[x x x 3] (just replace x with some sentinel)
obviously which 1 is the first element > 0 and not in the array.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*****y 的大作中提到】
: Is it possible the input array like this?
: 3 4 -1 1000
|
z**c
发帖数: 625 | 16 输入[1,2,3]，你的算法结果是什么？
【在 i**********e 的大作中提到】
: 基于你的方法再做一些优化.
: 没必要找最小的正数（因为是大于0，如果大于k的话就要）.
: 把每个数字 swap 到它的正确 index 去，如果是小于 0 或者大于 n-1 就跳过，直到
: 没的swap为止.
: For example,
: [3,4,-1,1]
: -> [1,4,-1,3] (3 与 1 对换）
: -> [4,1,-1,3] (1 与 4 对换）
: -> [x,1,-1,3] (跳过 4）
: -> [x,1,-1,3] (跳过 1，因为 1 已经在对的位置）
|
v*******1
发帖数: 10 | 17 这个方法是对的。
基本想法就是把每个positive的数i，放到index为i的位置上
这样放完之后再遍历一边数组，一旦看到array[i]!=i就表示i这个数是missing的
【在 s*******n 的大作中提到】
: # Pass 1, move every value to the position of its value
: for cursor in range(N):
: target = array[cursor]
: while target < N and target != array[target]:
: new_target = array[target]
: array[target] = target
: target = new_target
: # Pass 2, find first location where the index doesn't match the value
: for cursor in range(N):
: if array[cursor] != cursor:
|
i**********e
发帖数: 1145 | 18 恩，off by one error.
要把所有位置加一就好了。
另外，1 一下 和 n 以上的数字可以跳过。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 z**c 的大作中提到】
: 输入[1,2,3]，你的算法结果是什么？
|
j********x
发帖数: 2330 | 19 constant means extra space
...
in your definition, there cannot be any constant space algorithm...
【在 m****v 的大作中提到】
:
: well, but actually the space you will use is not 'constant'
: if the spec says 'no extra space', it is fine
: is it?
|
j********x
发帖数: 2330 | 20 牛啊。。。
【在 i**********e 的大作中提到】
: 恩，off by one error.
: 要把所有位置加一就好了。
: 另外，1 一下 和 n 以上的数字可以跳过。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
|
|
j********x
发帖数: 2330 | 21 你怎么得到这个思路的？还是挺巧妙的。。。
【在 g***s 的大作中提到】
: 没有重复的话，很容易。
: 1. 先找到最小的正数t
: 2. 对每一个数字，如果值k-t是0－n-1，就替换到位置k-t上去
: 3. 遍力找第一个不match的
|
b***e
发帖数: 1419 | 22 你这个貌似就是counting sort, 对值域有要求。无法是constant space。比如我最小
的数是
10000000000000，但是数组的长度只有1000000，似乎space要爆。
我感觉这个正解应该是问quick sort，每次抛掉一半(pivot前的长度小于pivot抛后一
半，否则抛前
一半)，最后平均是O(n)。
【在 g***s 的大作中提到】
: 没有重复的话，很容易。
: 1. 先找到最小的正数t
: 2. 对每一个数字，如果值k-t是0－n-1，就替换到位置k-t上去
: 3. 遍力找第一个不match的
|
g*********s
发帖数: 1782 | 23 握手。他的方法我没太看懂。但我想partition应该是可以的。
【在 b***e 的大作中提到】
: 你这个貌似就是counting sort, 对值域有要求。无法是constant space。比如我最小
: 的数是
: 10000000000000，但是数组的长度只有1000000，似乎space要爆。
: 我感觉这个正解应该是问quick sort，每次抛掉一半(pivot前的长度小于pivot抛后一
: 半，否则抛前
: 一半)，最后平均是O(n)。
|
i**********e
发帖数: 1145 | 24 他的方法不是 counting sort.
counting sort 需要另建一个 array，这个 in-place swap 就可以了.
这题 exploit 的就是在一个数组里最多只有 n 个不同的元素.
那么如果数组里最大的元素小于 n，很肯定就是数组里 1-n 的范围 少了至少一个数字
，也就是大于0而不在数组里的数字肯定在于 1-n 这个范围内.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 b***e 的大作中提到】
: 你这个貌似就是counting sort, 对值域有要求。无法是constant space。比如我最小
: 的数是
: 10000000000000，但是数组的长度只有1000000，似乎space要爆。
: 我感觉这个正解应该是问quick sort，每次抛掉一半(pivot前的长度小于pivot抛后一
: 半，否则抛前
: 一半)，最后平均是O(n)。
|
g**e
发帖数: 6127 | 25 他的方法是超过数组长度的就丢掉，是可以的
前面有人提到不找最小值直接做也是可以的
pivot的方法什么时候停止？
【在 g*********s 的大作中提到】
: 握手。他的方法我没太看懂。但我想partition应该是可以的。
|
b***e
发帖数: 1419 | 26 就Partition一遍恐怕不行吧。
【在 g*********s 的大作中提到】
: 握手。他的方法我没太看懂。但我想partition应该是可以的。
|
g**e
发帖数: 6127 | 27 没想明白，比如pivot=0, 得到-3, -1, 0, 2, 3, 1 抛哪一段？
【在 b***e 的大作中提到】
: 你这个貌似就是counting sort, 对值域有要求。无法是constant space。比如我最小
: 的数是
: 10000000000000，但是数组的长度只有1000000，似乎space要爆。
: 我感觉这个正解应该是问quick sort，每次抛掉一半(pivot前的长度小于pivot抛后一
: 半，否则抛前
: 一半)，最后平均是O(n)。
|
b***e
发帖数: 1419 | 28 你这个对，原帖的不对。超出长度抛掉是const space。
但是，我不喜欢这个方法，因为过于destructive。如前面那个[-1,3,4,1000]的例子，
你抛的只剩
3。如果题目稍变，加一个条件：不能丢失信息，你这个做法就完了。我那个partition
的做法仍然成
立。
【在 i**********e 的大作中提到】
: 他的方法不是 counting sort.
: counting sort 需要另建一个 array，这个 in-place swap 就可以了.
: 这题 exploit 的就是在一个数组里最多只有 n 个不同的元素.
: 那么如果数组里最大的元素小于 n，很肯定就是数组里 1-n 的范围 少了至少一个数字
: ，也就是大于0而不在数组里的数字肯定在于 1-n 这个范围内.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
i**d
发帖数: 357 | 29
大牛，能展开讲讲你的思路么？ 不太明白。
【在 b***e 的大作中提到】
: 你这个貌似就是counting sort, 对值域有要求。无法是constant space。比如我最小
: 的数是
: 10000000000000，但是数组的长度只有1000000，似乎space要爆。
: 我感觉这个正解应该是问quick sort，每次抛掉一半(pivot前的长度小于pivot抛后一
: 半，否则抛前
: 一半)，最后平均是O(n)。
|
i**********e
发帖数: 1145 | 30 你说得对，我这方法不能保存原来的数组元素.
我想了一会儿你说的 partition，这个 divide and conquer 的方向我完全没有思路.
divide and conquer 需要有很强的联合性，
例如你有两个数组A和数组B，怎么把这两个数组的答案联合到最终答案？
似乎没什么关系啊？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
partition
【在 b***e 的大作中提到】
: 你这个对，原帖的不对。超出长度抛掉是const space。
: 但是，我不喜欢这个方法，因为过于destructive。如前面那个[-1,3,4,1000]的例子，
: 你抛的只剩
: 3。如果题目稍变，加一个条件：不能丢失信息，你这个做法就完了。我那个partition
: 的做法仍然成
: 立。
|
|
|
g**e
发帖数: 6127 | 31 我也不明白， -3, -1, 0, 2, 1 pivit＝0，然后呢？
子，
【在 i**********e 的大作中提到】
: 你说得对，我这方法不能保存原来的数组元素.
: 我想了一会儿你说的 partition，这个 divide and conquer 的方向我完全没有思路.
: divide and conquer 需要有很强的联合性，
: 例如你有两个数组A和数组B，怎么把这两个数组的答案联合到最终答案？
: 似乎没什么关系啊？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: partition
|
g***s
发帖数: 3811 | 32 超过的只是skip。所有元素都不丢失。
partition
【在 b***e 的大作中提到】
: 你这个对，原帖的不对。超出长度抛掉是const space。
: 但是，我不喜欢这个方法，因为过于destructive。如前面那个[-1,3,4,1000]的例子，
: 你抛的只剩
: 3。如果题目稍变，加一个条件：不能丢失信息，你这个做法就完了。我那个partition
: 的做法仍然成
: 立。
|
b***e
发帖数: 1419 | 33 If you keep all, then you're simply doing counting sort (or a slight
variant). As a consequence, you cannot limit to constant space.
【在 g***s 的大作中提到】
: 超过的只是skip。所有元素都不丢失。
:
: partition
|
m****v
发帖数: 84 | 34
well, actually i mean, if the extra space (other than input) this
algorithm uses is constant (like O(10)), then the space complexity is
constant; if extra space not constant (like O(N^2)), then complexity not
constant.
i don't think this means 'constant means extra space' or 'there cannot be
any constant space algorithm...' as you said, :)
well, i guess you might mean we have to (at least) read all elements from
input in O(n). but merely doing this will not 'use' the input as space (in
which we can store or alter something) for algorithm.
anyway, the trick in this problem is to mess up the given array (if we
want to solve it in O(n) time)
【在 j********x 的大作中提到】
: constant means extra space
: ...
: in your definition, there cannot be any constant space algorithm...
|
b**********r
发帖数: 91 | 35 Uses 3 passes:
first pass set all non positives value to N+1 where N is the array size
second pass:
for each i in array
if (abs(i)>=0 and abs(i) < N)
array[abs(i)] = -abs (array[abs(i)])
third pass:
find the first index whose value is positive
O(n) with constant space
n)
【在 R***i 的大作中提到】
: 公司名就不说了
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
: 我给了2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of
: integers， time O(n), space O(n)。 但面试的人告诉我都不是最优解，有time O(n)
: , constant space的解。。。现在都没想明白，大家集思广益吧
|
m****v
发帖数: 84 | 36
这题的关键是从左往右扫描，一路上无视两类数：1）非正数；2）大于等于数组长度的
数。同时一路上
将遇到的小于数组长度的数，跟等于这个数的下标位置上的数互换。然后再扫描一次，
就知道答案了。
应该可以keep all，也不用多分配空间。
【在 b***e 的大作中提到】
: If you keep all, then you're simply doing counting sort (or a slight
: variant). As a consequence, you cannot limit to constant space.
|
b***e
发帖数: 1419 | 37 这个不用联合，就是二分法。找一个pivot, split一下：
pre_array, pivot, post_array
如果
1. pre_array.length < pivot，那么空子在前面，recursion on pre_array。
2. 否则空子在后面，recursion on post_array。
这招不能直接搞重复的情形。如果哦有重复，可以两招一起用:
2. 如果ihasleetcode_method(pre_array)找到的空子，return; otherwise,
recursion on (post_array).
这个不丢信息，而且期望为O(n).
【在 i**********e 的大作中提到】
: 你说得对，我这方法不能保存原来的数组元素.
: 我想了一会儿你说的 partition，这个 divide and conquer 的方向我完全没有思路.
: divide and conquer 需要有很强的联合性，
: 例如你有两个数组A和数组B，怎么把这两个数组的答案联合到最终答案？
: 似乎没什么关系啊？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: partition
|
m****v
发帖数: 84 | 38
期望...
【在 b***e 的大作中提到】
: 这个不用联合，就是二分法。找一个pivot, split一下：
: pre_array, pivot, post_array
: 如果
: 1. pre_array.length < pivot，那么空子在前面，recursion on pre_array。
: 2. 否则空子在后面，recursion on post_array。
: 这招不能直接搞重复的情形。如果哦有重复，可以两招一起用:
: 2. 如果ihasleetcode_method(pre_array)找到的空子，return; otherwise,
: recursion on (post_array).
: 这个不丢信息，而且期望为O(n).
|
b***e
发帖数: 1419 | 39 置换会冲掉原有的信息，导致信息的流失。除非你有一个很好的data backup plan。I
don't see
a trivial one.
【在 m****v 的大作中提到】
:
: 期望...
|
b***e
发帖数: 1419 | 40 Partition based algorithms have O(n*n) worst case. But in reality, it's
the fastest.
【在 m****v 的大作中提到】
:
: 期望...
|
|
|
m****v
发帖数: 84 | 41
I
同意，实际中肯定不应该把信息弄乱，不过如果从纯做题的角度看，这样应该可以吧。
【在 b***e 的大作中提到】
: 置换会冲掉原有的信息，导致信息的流失。除非你有一个很好的data backup plan。I
: don't see
: a trivial one.
|
b***e
发帖数: 1419 | 42 那么你认为interview question是偏实际多些呢，还是偏纯做题多些呢？如果我是考官
，不会仅仅
接受counting sort based algorithm.
【在 m****v 的大作中提到】
:
: I
: 同意，实际中肯定不应该把信息弄乱，不过如果从纯做题的角度看，这样应该可以吧。
|
g***s
发帖数: 3811 | 43 今天太晚，明天提供具体程序。只需要而外的一个临时变量，用来交换。
2n次比较，n次交换。
这个跟查找重复数字是一个思路。
【在 b***e 的大作中提到】
: If you keep all, then you're simply doing counting sort (or a slight
: variant). As a consequence, you cannot limit to constant space.
|
g*********s
发帖数: 1782 | 44 小板凳等大牛。
【在 g***s 的大作中提到】
: 今天太晚，明天提供具体程序。只需要而外的一个临时变量，用来交换。
: 2n次比较，n次交换。
: 这个跟查找重复数字是一个思路。
|
c***r
发帖数: 46 | 45 An alternative method. 先找数组中存在的最小的大于1的值。 把这个减一即可。
Amortized O(n), in place. Don't destory input values.
Think about this way first.
1) For all in input:
If value <= 1, value = LargePositive
2) Construct a min-heap. Output the root.
In fact, step 1) is not necessary. You just need to modify your comparator
function so that all values <=1 are treated as max. |
y****I
发帖数: 86 | 46 grass you so 无聊。
【在 g***s 的大作中提到】
: 今天太晚，明天提供具体程序。只需要而外的一个临时变量，用来交换。
: 2n次比较，n次交换。
: 这个跟查找重复数字是一个思路。
|
g***s
发帖数: 3811 | 47 public class MyTest2 {
static final int a[] = new int[]{-9,6,10000, 6, 3, 7, 1,2,5};
public static void main(String arg[]){
System.out.println("the min missing number is : " +
findMissingNum(a));
}
static private int findMissingNum(int a[]){
for (int i = 0 ; i< a.length; i++){
while (needMove(i,a))
move(i,a);
}
int i;
for (i = 0 ; i< a.length; i++){
if (a[i] != i+1 ) return i+1;
}
return a.length+1;
}
static private boolean needMove (int pos, int[] a){
return !(a[pos] == pos + 1 || a[pos] >= a.length || a[pos] <= 0
|| a[a[pos]-1] == a[pos] );
}
static private void move (int pos, int[] a){
int newPos = a[pos]-1;
a[pos] = a[newPos];
a[newPos] = newPos + 1;
}
}
证明：每次比较（call needMove），要么i＋＋，要么把一个数字move到正确的位置上
面。move
最多n次，i＋＋最多n次。所以，needMove最多２n次。
所以worst case ２n次比较(包含４个小比较)，n次move。
所有的move里面，都是swap。所以数据没丢失。
Q：是否题目会隐含条件：不能移动元素？
A：如果出题的人让你找第k大元素，是否你也不打算移动元素？这时一样的。除非专门
说明，一般数
组里大元素是可以移动，但不能丢失。
【在 g***s 的大作中提到】
: 今天太晚，明天提供具体程序。只需要而外的一个临时变量，用来交换。
: 2n次比较，n次交换。
: 这个跟查找重复数字是一个思路。
|
g***s
发帖数: 3811 | 48 haha, 你这么早就上班？然后泡bbs？
【在 y****I 的大作中提到】
: grass you so 无聊。
|
n********5
发帖数: 323 | 49 练习一下
public class FindMissNum {
/**
* @param args
*
* Find the missing number larger than 0.
*
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
// array elements are larger than 0.
int[] array0 = { 2, 4, 1, 9 };
int[] array1 = {1, 2,3,4};
for (int i = 0; i < array1.length; i++) {
System.out.println(array1[i]);
}
int missNum = FindNum(array1);
System.out.println("The missing num is " + missNum);
}
public static int FindNum(int[] array) {
if (array.length == 0 || array == null) {
return -1;
}
// 1 Pass
for (int i = 0; i < array.length; i++) {
if (0 < array[i] && array[i] < (array.length - 1)) {
//Suppose no duplicate integer.
int pos = array[i];
if(i != pos-1){
array[i] = array[pos-1];
array[pos-1] = pos;
}
}
}
for(int i=0; i
System.out.println("The element is " + array[i]);
}
// 2 Pass
for (int i = 0; i < array.length; i++) {
if (array[i]-1 != i) {
return array[i-1]+1;
}
}
return array.length + 1;
}
} |
g***s
发帖数: 3811 | 50 try array1 = { -1, 4 , 2, 1, 9 , 10 };
and you will get exception. -- after loop, you will get {-1,2,1,4,9,10}
which is wrong.
【在 n********5 的大作中提到】
: 练习一下
: public class FindMissNum {
: /**
: * @param args
: *
: * Find the missing number larger than 0.
: *
: */
: public static void main(String[] args) {
: // TODO Auto-generated method stub
|
|
|
c********l
发帖数: 8138 | 51 我觉得这题o(n) constant space无解
之前给的那个把值为i的元素替换到第i个位置上，虽然空间满足，但是时间复杂度绝对
不满足
n)
【在 R***i 的大作中提到】
: 公司名就不说了
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
: 我给了2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of
: integers， time O(n), space O(n)。 但面试的人告诉我都不是最优解，有time O(n)
: , constant space的解。。。现在都没想明白，大家集思广益吧
|
g***s
发帖数: 3811 | 52 我都给出cddes和证明了，被无视啊
我觉得这题o(n) constant space无解之前给的那个把值为i的元素替换到第i个位置上
，虽然空间满足，但是时间复杂度绝对不满足
★ Sent from iPhone App: iReader Mitbbs 6.0 - iPhone Lite
【在 c********l 的大作中提到】
: 我觉得这题o(n) constant space无解
: 之前给的那个把值为i的元素替换到第i个位置上，虽然空间满足，但是时间复杂度绝对
: 不满足
:
: n)
|
H*M
发帖数: 1268 | 53 这个怎么是const的space？
【在 g***s 的大作中提到】
: public class MyTest2 {
: static final int a[] = new int[]{-9,6,10000, 6, 3, 7, 1,2,5};
: public static void main(String arg[]){
: System.out.println("the min missing number is : " +
: findMissingNum(a));
: }
: static private int findMissingNum(int a[]){
: for (int i = 0 ; i< a.length; i++){
: while (needMove(i,a))
: move(i,a);
|
g***s
发帖数: 3811 | 54 只用了本身的数组空间+ const space
【在 H*M 的大作中提到】
: 这个怎么是const的space？
|
H*M
发帖数: 1268 | 55 我没细看你程序
但是
a(a(3))=a(20000)是const space?
【在 g***s 的大作中提到】
: 只用了本身的数组空间+ const space
|
g***s
发帖数: 3811 | 56 那再仔细看。
【在 H*M 的大作中提到】
: 我没细看你程序
: 但是
: a(a(3))=a(20000)是const space?
|
s*****y
发帖数: 897 | 57 仿照大牛的写了个C的
static int array[] = { 2, 4, 1, 9 };
//static int array[] = {-1, 4 , 2, 1, 9 , 10 };
int _tmain(int argc, _TCHAR* argv[])
{
int i;
int tmp;
int size = sizeof(array)/sizeof(int);
for (i = 0; i < size; ) {
if ((array[i] <= 0) || (array[i] > size)|| (array[i] == i+1)) {
i++;
continue;
}
/*switch array[i] and array[array[i]-1]*/
tmp = array[array[i]-1];
array[array[i]-1] = array[i];
array[i] = tmp;
}
for (i = 0; i < size; i++) {
if (array[i] != i+1)
printf("---------The missing number is %d========\r\n", i+1);
/*this is the missing number*/
}
return 0;
}
【在 g***s 的大作中提到】
: public class MyTest2 {
: static final int a[] = new int[]{-9,6,10000, 6, 3, 7, 1,2,5};
: public static void main(String arg[]){
: System.out.println("the min missing number is : " +
: findMissingNum(a));
: }
: static private int findMissingNum(int a[]){
: for (int i = 0 ; i< a.length; i++){
: while (needMove(i,a))
: move(i,a);
|
L*******e
发帖数: 2540 | |
g***s
发帖数: 3811 | 59 这个不对。仔细比较
【在 s*****y 的大作中提到】
: 仿照大牛的写了个C的
: static int array[] = { 2, 4, 1, 9 };
: //static int array[] = {-1, 4 , 2, 1, 9 , 10 };
: int _tmain(int argc, _TCHAR* argv[])
: {
: int i;
: int tmp;
: int size = sizeof(array)/sizeof(int);
: for (i = 0; i < size; ) {
: if ((array[i] <= 0) || (array[i] > size)|| (array[i] == i+1)) {
|
b***1
发帖数: 668 | 60 I warn you: If you do not delete this post, I will report your name to
Google HR Department. You violated Google's NDA policy which you have signed
when you were interviewed by Google. I give you a chance... |
|
|
m****t
发帖数: 555 | 61
signed
怎么还有这种人啊。你有本事去把creercup网站去关了不就一了百了了嘛。
【在 b***1 的大作中提到】
: I warn you: If you do not delete this post, I will report your name to
: Google HR Department. You violated Google's NDA policy which you have signed
: when you were interviewed by Google. I give you a chance...
|
v*****u
发帖数: 406 | 62
signed
啊，我还以为是个笑话呢？
这怎么知道是google，你怎么知道他的名字呢
楼主根本没有说是google的题目，是 *你* 泄漏出这是google的题，那是你的错吧？
真是我看到好伤心啊！这种事情对你自己有什么好处呢？
【在 b***1 的大作中提到】
: I warn you: If you do not delete this post, I will report your name to
: Google HR Department. You violated Google's NDA policy which you have signed
: when you were interviewed by Google. I give you a chance...
|
n********5
发帖数: 323 | 63 it's not a joke. period.
signed
【在 b***1 的大作中提到】
: I warn you: If you do not delete this post, I will report your name to
: Google HR Department. You violated Google's NDA policy which you have signed
: when you were interviewed by Google. I give you a chance...
|
c*******o
发帖数: 1357 | 64 放心，这个id是那天一直在起哄的
【在 v*****u 的大作中提到】
:
: signed
: 啊，我还以为是个笑话呢？
: 这怎么知道是google，你怎么知道他的名字呢
: 楼主根本没有说是google的题目，是 *你* 泄漏出这是google的题，那是你的错吧？
: 真是我看到好伤心啊！这种事情对你自己有什么好处呢？
|
s*****y
发帖数: 897 | 65 大牛，我测试过几个input都对的阿，可否给个反例阿。
你的code这里
static private boolean needMove (int pos, int[] a){
return !(a[pos] == pos + 1 || a[pos] >= a.length || a[pos] <= 0
|| a[a[pos]-1] == a[pos] );
}
我的确没有看懂这个a[a[pos]-1] == a[pos]。 请指点。
谢谢。
【在 g***s 的大作中提到】
: 这个不对。仔细比较
|
g***s
发帖数: 3811 | 66 1. if 和 while的区别。你把当前的换走，换过来的元素还需要继续处理。不能直接往
下跳
2. 如果要换过去的地方本身值就是当前值，就没有必要换（这是如果里面有重复需要
考虑的）
【在 s*****y 的大作中提到】
: 大牛，我测试过几个input都对的阿，可否给个反例阿。
: 你的code这里
: static private boolean needMove (int pos, int[] a){
: return !(a[pos] == pos + 1 || a[pos] >= a.length || a[pos] <= 0
: || a[a[pos]-1] == a[pos] );
: }
: 我的确没有看懂这个a[a[pos]-1] == a[pos]。 请指点。
: 谢谢。
|
s*****y
发帖数: 897 | 67 我的code换了元素后没有直接往下跳，而是反复处理当前位置的数据，直到
array[i] == i+1 才会向下跳的，所以跟你的code有点不一样。
for (i = 0; i < size; ) {
if ((array[i] <= 0) || (array[i] > size)|| (array[i] == i+1)) {
i++;
continue;
}
/*switch array[i] and array[array[i]-1]*/
tmp = array[array[i]-1];
array[array[i]-1] = array[i];
array[i] = tmp;
}
【在 g***s 的大作中提到】
: 1. if 和 while的区别。你把当前的换走，换过来的元素还需要继续处理。不能直接往
: 下跳
: 2. 如果要换过去的地方本身值就是当前值，就没有必要换（这是如果里面有重复需要
: 考虑的）
|
y****I
发帖数: 86 | 68 我就说你无聊嘛。 除了面试的时候一般不太写这种code吧。 维护性比较差，大牛一走
换个菜一点的一改就出问题。
【在 g***s 的大作中提到】
: 我都给出cddes和证明了，被无视啊
:
: 我觉得这题o(n) constant space无解之前给的那个把值为i的元素替换到第i个位置上
: ，虽然空间满足，但是时间复杂度绝对不满足
: ★ Sent from iPhone App: iReader Mitbbs 6.0 - iPhone Lite
|
n********5
发帖数: 323 | 69 无聊一下，，，thanks for point it out. i just add a check for the second
pass. it
works. the result of the first pass does not need to be sorted.
here are the codes.
public static int FindNum(int[] array) {
if (array.length == 0 || array == null) {
return -1;
}
// 1 Pass
for (int i = 0; i < array.length; i++) {
if (0 < array[i] && array[i] < (array.length - 1)) {
// Suppose no duplicate integer.
int pos = array[i];
if (i != pos - 1) {
array[i] = array[pos - 1];
array[pos - 1] = pos;
}
}
}
for (int i = 0; i < array.length; i++) {
System.out.println("The element is " + array[i]);
}
// 2 Pass
for (int i = 0; i < array.length; i++) {
if (array[i] > 0 && (array[i] - 1 != i)) {
return array[i - 1] + 1;
}
}
return array.length + 1;
}
【在 g***s 的大作中提到】
: try array1 = { -1, 4 , 2, 1, 9 , 10 };
: and you will get exception. -- after loop, you will get {-1,2,1,4,9,10}
: which is wrong.
|
g***s
发帖数: 3811 | 70 哦。那是否考虑了换回来还是相同元素？
【在 s*****y 的大作中提到】
: 我的code换了元素后没有直接往下跳，而是反复处理当前位置的数据，直到
: array[i] == i+1 才会向下跳的，所以跟你的code有点不一样。
: for (i = 0; i < size; ) {
: if ((array[i] <= 0) || (array[i] > size)|| (array[i] == i+1)) {
: i++;
: continue;
: }
:
: /*switch array[i] and array[array[i]-1]*/
: tmp = array[array[i]-1];
|
|
|
g***s
发帖数: 3811 | 71 这不是我设计的题目。
不过，可读性比节约一些空间要重要。
【在 y****I 的大作中提到】
: 我就说你无聊嘛。 除了面试的时候一般不太写这种code吧。 维护性比较差，大牛一走
: 换个菜一点的一改就出问题。
|
s*****y
发帖数: 897 | 72 can you give me an input example?
【在 g***s 的大作中提到】
: 哦。那是否考虑了换回来还是相同元素？
|
g***s
发帖数: 3811 | 73 5个2
【在 s*****y 的大作中提到】
: can you give me an input example?
|
s*****y
发帖数: 897 | 74 Thanks da niu. My code die in the dead loop. Did not consider througly.
【在 g***s 的大作中提到】
: 5个2
|
R***i
发帖数: 78 | 75 我是楼主，今天收到此公司的据信。。。
这公司onsite一共面了三轮，除了这道题这轮外都是完美发挥，没被抓到一点bug，不
过还是挂在这道题目上了。。。希望对其他的同学有所帮助吧。。。
。。。找工作真是个需要强大精神力的过程，不断的被一次次打倒。。。求安慰 |
g***s
发帖数: 3811 | 76 有时候塞翁失马，可能后面反而找到更好的。
当年我一个朋友，就是在都快要准备回国的时候拿到一个top 5的hedge fund的offer。 |
v*****u
发帖数: 406 | 77
能想到这个题的，肯定有大公司好offer等着你。
【在 R***i 的大作中提到】
: 我是楼主，今天收到此公司的据信。。。
: 这公司onsite一共面了三轮，除了这道题这轮外都是完美发挥，没被抓到一点bug，不
: 过还是挂在这道题目上了。。。希望对其他的同学有所帮助吧。。。
: 。。。找工作真是个需要强大精神力的过程，不断的被一次次打倒。。。求安慰
|
P**********c
发帖数: 3417 | 78 什么公司啊，感觉他们的目的就是要把你问倒一样，太bt了。
【在 R***i 的大作中提到】
: 我是楼主，今天收到此公司的据信。。。
: 这公司onsite一共面了三轮，除了这道题这轮外都是完美发挥，没被抓到一点bug，不
: 过还是挂在这道题目上了。。。希望对其他的同学有所帮助吧。。。
: 。。。找工作真是个需要强大精神力的过程，不断的被一次次打倒。。。求安慰
|
a********m
发帖数: 15480 | 79 // patpat & bless
找工作确实很累。。。sigh
【在 R***i 的大作中提到】
: 我是楼主，今天收到此公司的据信。。。
: 这公司onsite一共面了三轮，除了这道题这轮外都是完美发挥，没被抓到一点bug，不
: 过还是挂在这道题目上了。。。希望对其他的同学有所帮助吧。。。
: 。。。找工作真是个需要强大精神力的过程，不断的被一次次打倒。。。求安慰
|
