想让老公转行 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

想让老公转行

想让老公转行# Biology - 生物学

o*y2016-11-20 08:11

1 楼

题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
版上找到的题据说有time O(n), constant space的解
讨论一下哈

y*82016-11-20 08:11

2 楼

我看他这辈子没戏走学术了
认真请教各位如果他每天拿出三个五个小时从零开始学习怎么做才能转行去it
coding 我养家很辛苦跳槽也不敢他又是个逃避社会型的闷头做实验做得也不好我
想做research先把这条路的可能性展示给他看看不然我太悲催了

e*r2016-11-20 08:11

3 楼

bool array [] = {T, T, T, T, T, T, T, T, T, …}
unsorted int array
int array2 [] = {3, 1, 2, 0, -1, …}
for(int i = 0; i < array2.size(); i++)
{
if(array2[i] > 0)
array[array2[i]] = false;
}
for(int i = 0; i < array.size(); i++)
if(array[i])
return i;
刚想的答案，看一下符合你的要求吗.

【在 o*******y 的大作中提到】

: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
: 版上找到的题据说有time O(n), constant space的解
: 讨论一下哈

h*l2016-11-20 08:11

4 楼

有些it coding也需要专业背景，就是说你没学过那个专业的课，也是coding不出来的。
不怎么需要专业背景的，可能去一些机构培训几个月就差不多能掌握基础知识，但是你
老公年纪
估计不小了，现在才开始，没什么经验也比较难入行。最好有华人帮忙。

【在 y**********8 的大作中提到】

: 我看他这辈子没戏走学术了
: 认真请教各位如果他每天拿出三个五个小时从零开始学习怎么做才能转行去it
: coding 我养家很辛苦跳槽也不敢他又是个逃避社会型的闷头做实验做得也不好我
: 想做research先把这条路的可能性展示给他看看不然我太悲催了

S*e2016-11-20 08:11

5 楼

我觉得可以用bit vector，size就是array size，扫一遍array，如果array中的整数在
bit vector之内，相应的bit变成1，之后再扫一遍bit vector，第一个0表示最小的不
在此array的数。

【在 o*******y 的大作中提到】

g*02016-11-20 08:11

6 楼

现在IT科班出来的都找不到工作，就别想这条路了。如果能混吃等死做一辈子千老就别
乱动了。

i*h2016-11-20 08:11

7 楼

数组长N, 那么答案肯定是在 1...N+1之间
假定可以改变原数组
用二分法

x*e2016-11-20 08:11

8 楼

想要加入转行计算机群的话加我微_信 kevin2016w_e_c_h_a_t (去掉下划线）

【在 y**********8 的大作中提到】

i*h2016-11-20 08:11

9 楼

如果数组里有相同数字
我的解就不是O(N)

【在 i***h 的大作中提到】

: 数组长N, 那么答案肯定是在 1...N+1之间
: 假定可以改变原数组
: 用二分法

d*s2016-11-20 08:11

10 楼

叫你老公自己来问，这种事情都要你替他问估计转行难度比较大
如果有啥问题可以叫你老公私信我，我正在转行路上

【在 y**********8 的大作中提到】

o*y2016-11-20 08:11

11 楼

度娘的答案。。。
利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于
等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为
m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
MIN-AVAILABLE-NUM(A, low, up)
if(low == up) return low
m = (low + up) / 2
split = partition(A, low, up, m)
if a[split] == m
then return MIN-AVAILABLE-NUM(A, low, split)
else return MIN-AVAILABLE-NUM(A, split+1, up)
这里递归式为：T(n) = T(n/2) + O(n)，根据主定理的第三种情况，复杂度为O(n)，其
实也就是一个等比数列：n + n/2 + n/4...
但是，此处因为用到递归，所以空间复杂度其实是O(Lgn)，所以可以用循环来代替：
MIN-AVAILABLE-NUM(A, low, up)
while low != up
m = (low + up) / 2
split = partition(low, up, m)
if A[split] == m
then low = split + 1
else up = split - 1
return low

o*y2016-11-20 08:11

12 楼

但有重复元素貌似有问题啊比如 4 4 4 4 5 6 7 8

i*h2016-11-20 08:11

13 楼

你可以另外做个循环处理这种情况, 还是O(N)

【在 o*******y 的大作中提到】

: 但有重复元素貌似有问题啊比如 4 4 4 4 5 6 7 8

e*r2016-11-20 08:11

14 楼

你说的是你贴的那个答案还是指俺说的那个，俺的那个可以应对重复元素.

【在 o*******y 的大作中提到】

: 但有重复元素貌似有问题啊比如 4 4 4 4 5 6 7 8

i*h2016-11-20 08:11

15 楼

你的不是 time O(n), constant space的解

【在 e********r 的大作中提到】

: 你说的是你贴的那个答案还是指俺说的那个，俺的那个可以应对重复元素.

e*r2016-11-20 08:11

16 楼

你是说不是constant space吗.

【在 i***h 的大作中提到】

: 你的不是 time O(n), constant space的解

i*h2016-11-20 08:11

17 楼

right

【在 e********r 的大作中提到】

: 你是说不是constant space吗.

l*i2016-11-20 08:11

18 楼

Use 0 to partition your array, the same idea as partition for quicksort

e*r2016-11-20 08:11

19 楼

请问能把partition funciton也贴出来吗，谢谢哈.

【在 o*******y 的大作中提到】

: 度娘的答案。。。
: 利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
: 取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于
: 等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为
: m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
: MIN-AVAILABLE-NUM(A, low, up)
: if(low == up) return low
: m = (low + up) / 2
: split = partition(A, low, up, m)
: if a[split] == m

y*n2016-11-20 08:11

20 楼

worse case is not T(n/2)+O(n). Is T(n-1)+O(n). And use partition cannot
handle negative number.

【在 o*******y 的大作中提到】

y*n2016-11-20 08:11

21 楼

结果必然在0到n+1之中。我们可以这样，扫描一遍数组，如果a[i]上的数为m，就找到a
[m]看里面的数是什么。如果是a[m]不是m我们就把a[i]a[m]换个位置。如果a[i]<0 or
>n就不要找a[m]了。这样一来最后大小为m的必然在a[m]位置上，如果a[m]位置上不为m
，那么这个m就是我们要找的值了。空间0时间O(n)
public static int getFirstPositive(int[] a) {
int i = 0;
while (i < a.length) {
int m = a[i];
if (m>=0 && mint tmp = a[m];
a[m] = a[i];
a[i] = tmp;
}else i++;
}

for(i = 1;i< a.length;i++){
if(a[i] != i) return i;
}
return a.length;
}

public static void main(String [] args){
int[] t1 = {1,2,0};
int[] t2 = {3,4,-1,1};
System.out.println(getFirstPositive(t1));
System.out.println(getFirstPositive(t2));
}

S*e2016-11-20 08:11

22 楼

好方法。我之前说的那个没注意到const space。

到a
or
为m

【在 y*****n 的大作中提到】

: 结果必然在0到n+1之中。我们可以这样，扫描一遍数组，如果a[i]上的数为m，就找到a
: [m]看里面的数是什么。如果是a[m]不是m我们就把a[i]a[m]换个位置。如果a[i]<0 or
: >n就不要找a[m]了。这样一来最后大小为m的必然在a[m]位置上，如果a[m]位置上不为m
: ，那么这个m就是我们要找的值了。空间0时间O(n)
: public static int getFirstPositive(int[] a) {
: int i = 0;
: while (i < a.length) {
: int m = a[i];
: if (m>=0 && m: int tmp = a[m];

w*o2016-11-20 08:11

23 楼

你的方法很好。
不过我发现了一个小的bug,
就是最后的处理，如果a[1],..., a[n-1]都有相应的值1, ..., n-1, 这时应该在检查
一下a[0],如果a[0]是n,的话，应该返回n+1,可是你的程序返回n,
比如{3, 1, 2},最后的救过应该是4，而不应该是3.

到a
or
为m

【在 y*****n 的大作中提到】

q*x2016-11-20 08:11

24 楼

走火入魔。

【在 o*******y 的大作中提到】

S*Y2016-11-20 08:11

25 楼

啥意思？

【在 q****x 的大作中提到】

: 走火入魔。

c*z2016-11-20 08:11

26 楼

思路同 yezhuen。
#include
#define V(i) (i + 1) /* Expected value of index i */
#define I(x) (x - 1) /* Expected index of value x */
int go(int *x, int n)
{
int i, t;
for (i = 0; i < n; i ++) {
while (x[i] > 0 && x[i] <= n &&
x[i] != V(i) &&
x[I(x[i])] != x[i]) {
t = I(x[i]);
x[i] = x[t];
x[t] = V(t);
}
}
for (i = 1; i < n; i ++) {
if (x[i] != V(i)) {
return V(i);
}
}
return V(n);
}
int main()
{
int x[4] = {3, 4, -1, 1};
printf("%d\n", go(x, 4));
return 0;
}

b*u2016-11-20 08:11

27 楼

array的size是2 billion。你打算说服考官这是O(1)么？

【在 e********r 的大作中提到】

: 请问能把partition funciton也贴出来吗，谢谢哈.

P*y2016-11-20 08:11

28 楼

这个对于有重复的数就不能处理了
比如4 2 3 4
返回的会是4

到a
or
为m

【在 y*****n 的大作中提到】

P*y2016-11-20 08:11

29 楼

刚想错了，返回应该是1
这算法对的

【在 P*******y 的大作中提到】

: 这个对于有重复的数就不能处理了
: 比如4 2 3 4
: 返回的会是4
:
: 到a
: or
: 为m