由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - unsorted int array怎么找到第一个大于0,并且不在此array的数
相关主题
新鲜C3 energy面经老问题了,网上竟然找不到答案
两道2009算法题找2个sorted array中的第K小的元素,有O(lgn)方法吗?
这题有最优解法么两个Sorted Array,找K smallest element
问一道算法题问一下deep copy和shallow copy的问题(C#)
问个面试题Find the intersection of two sorted arrays【扩展】
find median for k sorted arrays问个微软面试题
divide array into two, sum of difference is min in O(N)请问G一题
被Facebook的面试的一道题目难倒了请教一下external sorting的问题
相关话题的讨论汇总
话题: int话题: array话题: return话题: expected话题: unsorted
1 (共1页)
o*******y
发帖数: 115
1
题目是给定一个unsorted int array, 怎么找到第一个大于0,并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
版上找到的题 据说有time O(n), constant space的解
讨论一下哈
e********r
发帖数: 2352
2
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的解
: 讨论一下哈

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

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

i***h
发帖数: 12655
4
数组长N, 那么答案肯定是在 1...N+1之间
假定可以改变原数组
用二分法
i***h
发帖数: 12655
5
如果数组里有相同数字
我的解就不是O(N)

【在 i***h 的大作中提到】
: 数组长N, 那么答案肯定是在 1...N+1之间
: 假定可以改变原数组
: 用二分法

o*******y
发帖数: 115
6
度娘的答案。。。
利用快速排序的原理,我们可以在不使用额外数组的情况下达到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*******y
发帖数: 115
7
但有重复元素貌似有问题啊 比如 4 4 4 4 5 6 7 8
i***h
发帖数: 12655
8
你可以另外做个循环处理这种情况, 还是O(N)

【在 o*******y 的大作中提到】
: 但有重复元素貌似有问题啊 比如 4 4 4 4 5 6 7 8
e********r
发帖数: 2352
9
你说的是你贴的那个答案还是指俺说的那个,俺的那个可以应对重复元素.

【在 o*******y 的大作中提到】
: 但有重复元素貌似有问题啊 比如 4 4 4 4 5 6 7 8
i***h
发帖数: 12655
10
你的不是 time O(n), constant space的解

【在 e********r 的大作中提到】
: 你说的是你贴的那个答案还是指俺说的那个,俺的那个可以应对重复元素.
相关主题
find median for k sorted arrays老问题了,网上竟然找不到答案
divide array into two, sum of difference is min in O(N)找2个sorted array中的第K小的元素,有O(lgn)方法吗?
被Facebook的面试的一道题目难倒了两个Sorted Array,找K smallest element
e********r
发帖数: 2352
11
你是说不是constant space吗.

【在 i***h 的大作中提到】
: 你的不是 time O(n), constant space的解
i***h
发帖数: 12655
12
right

【在 e********r 的大作中提到】
: 你是说不是constant space吗.
l***i
发帖数: 1309
13
Use 0 to partition your array, the same idea as partition for quicksort
e********r
发帖数: 2352
14
请问能把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*****n
发帖数: 243
15

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

【在 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*****n
发帖数: 243
16
结果必然在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];
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*****e
发帖数: 229
17
好方法。我之前说的那个没注意到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****o
发帖数: 2260
18
你的方法很好。
不过我发现了一个小的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 的大作中提到】
: 结果必然在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];

q****x
发帖数: 7404
19
走火入魔。

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

S**Y
发帖数: 136
20
啥意思?

【在 q****x 的大作中提到】
: 走火入魔。
相关主题
问一下deep copy和shallow copy的问题(C#)请问G一题
Find the intersection of two sorted arrays【扩展】请教一下external sorting的问题
问个微软面试题a question
c*z
发帖数: 86
21
思路同 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***u
发帖数: 12010
22
array的size是2 billion。你打算说服考官这是O(1)么?

【在 e********r 的大作中提到】
: 请问能把partition funciton也贴出来吗,谢谢哈.
P*******y
发帖数: 168
23
这个对于有重复的数就不能处理了
比如4 2 3 4
返回的会是4

到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];

P*******y
发帖数: 168
24
刚想错了,返回应该是1
这算法对的

【在 P*******y 的大作中提到】
: 这个对于有重复的数就不能处理了
: 比如4 2 3 4
: 返回的会是4
:
: 到a
: or
: 为m

1 (共1页)
相关主题
请教一下external sorting的问题问个面试题
a questionfind median for k sorted arrays
贡献几道CS电面题divide array into two, sum of difference is min in O(N)
找最大俩数的代码怎么写?被Facebook的面试的一道题目难倒了
新鲜C3 energy面经老问题了,网上竟然找不到答案
两道2009算法题找2个sorted array中的第K小的元素,有O(lgn)方法吗?
这题有最优解法么两个Sorted Array,找K smallest element
问一道算法题问一下deep copy和shallow copy的问题(C#)
相关话题的讨论汇总
话题: int话题: array话题: return话题: expected话题: unsorted