s*****w
发帖数: 26 | 1 面试官的问题：
将1-N，在随机排序在一个数组中。将其中两个数，换成0。
如何快速发现是哪两个数被换掉了？
求大牛解答！ |
y***n
发帖数: 1594 | |
u*****o
发帖数: 1224 | 3 这个用swap应该可以做吧。碰到0就skip,非0的就一直swap，一直到它占在应该在的位
置上。再扫一遍，0在的位置就是被换掉的数。 |
c********p
发帖数: 1969 | |
u*****o
发帖数: 1224 | 5 你今天好点没？不难受了吧？
【在 c********p 的大作中提到】
: 为什么这个题最近考这么多？这个能干什么用？
|
t**********h
发帖数: 2273 | 6 leetcode question 41.好好做做，好几种做法。leetcode这题的限制是最多的，如果
没有限制，那么解法更多。
【在 s*****w 的大作中提到】
: 面试官的问题：
: 将1-N，在随机排序在一个数组中。将其中两个数，换成0。
: 如何快速发现是哪两个数被换掉了？
: 求大牛解答！
|
c********p
发帖数: 1969 | 7 大波妹你真甜！
我昨天半夜吃了片药，半夜就精神了。。。
【在 u*****o 的大作中提到】
: 你今天好点没？不难受了吧？
|
s*******n
发帖数: 305 | 8 用hash的话， time O(n), Space O(n)
public void findTwoMiss2(int[] C) {
HashMap map = new HashMap();
int ret = 0;
for (int i = 0; i < C.length; i++)
map.put(C[i], C[i]);
for (int i = 1; i <= C.length + 2; i++) {
if (map.get(i) == null) {
System.out.println(i);
}
}
} |
s*******n
发帖数: 305 | 9 或者先sort, 再check neighbor的 话， time O(nlogn), Space O(1), 不过都取决于
sort 的O(sort) |
s********r
发帖数: 403 | 10 磁盘阵列，数据恢复
但是2个block failure 用的是 reed solomon coding
【在 c********p 的大作中提到】
: 为什么这个题最近考这么多？这个能干什么用？
|
|
|
s********g
发帖数: 126 | 11 if you can modify elements,you can realize it with time complexity O(n). set
arr[|arr[i]|] to negative, and check which two missing elements, and
finally set arr back to non-negative. Be careful with array index boundary. |
r*****e
发帖数: 792 | 12 用额外的memory解法都不好吧
用xor不就行了？比只找一个的难点，
但意思一样的
【在 s*****w 的大作中提到】
: 面试官的问题：
: 将1-N，在随机排序在一个数组中。将其中两个数，换成0。
: 如何快速发现是哪两个数被换掉了？
: 求大牛解答！
|
u*****o
发帖数: 1224 | 13 激动了,这题也能用xor做? 大牛指点!!
【在 r*****e 的大作中提到】
: 用额外的memory解法都不好吧
: 用xor不就行了？比只找一个的难点，
: 但意思一样的
|
s*******n
发帖数: 305 | 14 同样膜拜， 一碰到位运算的感觉就相碰到了递归， 简单还行， 稍微复杂一点只能背
题了。。。 |
s*********n
发帖数: 191 | 15 这个题目的O(N)+O(1)解法太多了啊，哪需要递归和排序什么。
1，都给了数据范围那最直接的就是桶排序啊，就是leetcode那道题的所谓swap的解法。
2，再笨一点的方法可以在知道了x+y和x*y求取一元二次方程也很快啊，一次遍历完成
。缺点是容易溢出。
3，再或者用xor也可以啊，知道了x^y的值，再根据x^y中某个1的位置，对原数组分成
两类元
素分别进行xor，两遍遍历。也可以直接求出x和y啊。
【在 s*****w 的大作中提到】
: 面试官的问题：
: 将1-N，在随机排序在一个数组中。将其中两个数，换成0。
: 如何快速发现是哪两个数被换掉了？
: 求大牛解答！
|
l*******0
发帖数: 63 | 16 想出两种思路，都是O(N)的time复杂度。请看注释。
public class HelloWorld{
//Idea：put every element into its right position. which means input[i]
is placed at input[i]-1. Then if input[i]==0, then i+1 is one missing
number.
//this approach modifies the original array.
//O(N) time
public static void printMissing(int[] input){
for(int i=0;i
while(i+1
swap(input, i, input[i]-1);
}
}
for(int i=0;i
if(input[i]==0) System.out.println(i+1);
}
}
// Idea：suppose a and b are missing.
//First get a XOR b
//Find right-most different bit of a, b (say bit k);then seperate
array into two parts:
//either kth bit is 0 or 1. two numbers fall into different parts.
//do xor respectively to get two missing numbers
public static void printMissing2(int[] input){
int aXORb=0;
for(int i=0;i
aXORb^=input[i]^(i+1);
}
int mask=aXORb-(aXORb&(aXORb-1));
int res[]=new int[2];
for(int i=0;i
if((input[i]&mask)==0){
res[0]=res[0]^input[i];
}else{
res[1]=res[1]^input[i];
}
}
for(int i=0;i
if(((i+1)&mask)==0){
res[0]=res[0]^(i+1);
}else{
res[1]=res[1]^(i+1);
}
}
//the above two loops can be combined. Here only for explanation
purpose I seperate the two.
System.out.println(res[0]);
System.out.println(res[1]);
}
public static void main(String []args){
int A[]={9,5,3,0,2,6,7,0,1,10};
printMissing2(A);
printMissing(A);
System.out.println("Hello World");
}
static void swap(int[]a, int i, int j){
if(i!=j){
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
}
【在 s*****w 的大作中提到】
: 面试官的问题：
: 将1-N，在随机排序在一个数组中。将其中两个数，换成0。
: 如何快速发现是哪两个数被换掉了？
: 求大牛解答！
|
c********p
发帖数: 1969 | 17 好深奥。。。
最近看好多人被问，我自己也被问过。。。
【在 s********r 的大作中提到】
: 磁盘阵列，数据恢复
: 但是2个block failure 用的是 reed solomon coding
|
u*****o
发帖数: 1224 | 18 我太喜欢你第二个solution了，知道x+y=a, x*y=b,
那么 x = (a+sqrt(a^2-b))/2, 初中经常解的方程组。。多少年不再用这个公式了，老
泪纵横啊。。
法。
【在 s*********n 的大作中提到】
: 这个题目的O(N)+O(1)解法太多了啊，哪需要递归和排序什么。
: 1，都给了数据范围那最直接的就是桶排序啊，就是leetcode那道题的所谓swap的解法。
: 2，再笨一点的方法可以在知道了x+y和x*y求取一元二次方程也很快啊，一次遍历完成
: 。缺点是容易溢出。
: 3，再或者用xor也可以啊，知道了x^y的值，再根据x^y中某个1的位置，对原数组分成
: 两类元
: 素分别进行xor，两遍遍历。也可以直接求出x和y啊。
|
l****i
发帖数: 2772 | 19 这个方法有可能溢出，面试的时候，要小心。
【在 u*****o 的大作中提到】
: 我太喜欢你第二个solution了，知道x+y=a, x*y=b,
: 那么 x = (a+sqrt(a^2-b))/2, 初中经常解的方程组。。多少年不再用这个公式了，老
: 泪纵横啊。。
:
: 法。
|
r*****e
发帖数: 792 | 20 let me dig my solution out later.
have not touched my interview code base for a while.
【在 u*****o 的大作中提到】
: 激动了,这题也能用xor做? 大牛指点!!
|
|
|
S*******w
发帖数: 24236 | 21 def findMissingTwo(numList, N):
summ = 0
for num in numList:
summ += num
summOfMissingTwo = (N+1)*N/2 - summ
summ = 0
M = summOfMissingTwo/2
for num in numList:
if num <= M:
summ += num
a = (M+1)*M/2 - summ
b = summOfMissingTwo - a
print "The missing two are:%d and %d)"%(a, b)
numList = [1, 2, 3, 4, 0, 6, 0, 8, 9, 10]
findMissingTwo(numList, len(numList))
【在 s*****w 的大作中提到】
: 面试官的问题：
: 将1-N，在随机排序在一个数组中。将其中两个数，换成0。
: 如何快速发现是哪两个数被换掉了？
: 求大牛解答！
|
s********r
发帖数: 403 | 22 可以实现 (K+N), N 个数据块 fail，
本质上是解线性方程组，
但是为了避免浮点数运算带来的误差，是在Galois field 上进行运算的，不使用乘除
指令集
【在 c********p 的大作中提到】
: 好深奥。。。
: 最近看好多人被问，我自己也被问过。。。
|
u*****o
发帖数: 1224 | 23 收到! 多谢提醒:)
【在 l****i 的大作中提到】
: 这个方法有可能溢出，面试的时候，要小心。
|
u*****o
发帖数: 1224 | 24 老鲨，你说的reed solomon coding和galois field我都不太懂。我想问问你你的意思
是不是说，在实际工作中碰到此类问题（比如你说的很多block里2个data block fail
，找出这两个block),解法是解方程的那个办法，而不是那个xor的办法。我一直都觉得
bit operations虽然快，但是野路子，不像是会被大规模使用的赶脚。。。
【在 s********r 的大作中提到】
: 可以实现 (K+N), N 个数据块 fail，
: 本质上是解线性方程组，
: 但是为了避免浮点数运算带来的误差，是在Galois field 上进行运算的，不使用乘除
: 指令集
|
c********p
发帖数: 1969 | 25 这个方法可行么？最多要扫几遍？
我当时答的就是这个，可惜面我的人智商是硬伤啊。。。
【在 u*****o 的大作中提到】
: 这个用swap应该可以做吧。碰到0就skip,非0的就一直swap，一直到它占在应该在的位
: 置上。再扫一遍，0在的位置就是被换掉的数。
|
c********p
发帖数: 1969 | 26 你说的这两个面试我都答了。。。
于
【在 s*******n 的大作中提到】
: 或者先sort, 再check neighbor的 话， time O(nlogn), Space O(1), 不过都取决于
: sort 的O(sort)
|
u*****o
发帖数: 1224 | 27 扫两遍吧，第一遍swap，第二遍找0.。
的确说清楚不容易啊。。
【在 c********p 的大作中提到】
: 这个方法可行么？最多要扫几遍？
: 我当时答的就是这个，可惜面我的人智商是硬伤啊。。。
|
u*****o
发帖数: 1224 | 28 甜甜好厉害。。好多面试的赶脚～～～
【在 c********p 的大作中提到】
: 你说的这两个面试我都答了。。。
:
: 于
|
s********r
发帖数: 403 | 29 实际工作中，要考虑溢出，应当用xor的方法，不然设计上有问题，就不能用了。
如果面试，可以用一个基本能 work，思路正确的方法混过去，只要面试官没规定。
然后顺路提一下还有别的方法。
fail
【在 u*****o 的大作中提到】
: 老鲨，你说的reed solomon coding和galois field我都不太懂。我想问问你你的意思
: 是不是说，在实际工作中碰到此类问题（比如你说的很多block里2个data block fail
: ，找出这两个block),解法是解方程的那个办法，而不是那个xor的办法。我一直都觉得
: bit operations虽然快，但是野路子，不像是会被大规模使用的赶脚。。。
|
c********p
发帖数: 1969 | 30 可是，第一遍的时候，就没有跳回去，然后露掉的么？
有完整的代码么？偶来研究一下。
【在 u*****o 的大作中提到】
: 扫两遍吧，第一遍swap，第二遍找0.。
: 的确说清楚不容易啊。。
|
|
|
t**********h
发帖数: 2273 | 31 swap最多一遍。
在swap的时候做两个检查，一个当前的A[i]上不是正确的数，另一个是A[A[i]-1]也不
是A[i],这样就能避免重复的swap。当然A[i]还要在范围内1 to N
【在 c********p 的大作中提到】
: 这个方法可行么？最多要扫几遍？
: 我当时答的就是这个，可惜面我的人智商是硬伤啊。。。
|
c********p
发帖数: 1969 | 32 没。。。。
【在 u*****o 的大作中提到】
: 甜甜好厉害。。好多面试的赶脚～～～
|
c********p
发帖数: 1969 | 33 求个完整的code我研究研究。。。
【在 t**********h 的大作中提到】
: swap最多一遍。
: 在swap的时候做两个检查，一个当前的A[i]上不是正确的数，另一个是A[A[i]-1]也不
: 是A[i],这样就能避免重复的swap。当然A[i]还要在范围内1 to N
|
a********m
发帖数: 15480 | 34 一遍应该不可能。
【在 t**********h 的大作中提到】
: swap最多一遍。
: 在swap的时候做两个检查，一个当前的A[i]上不是正确的数，另一个是A[A[i]-1]也不
: 是A[i],这样就能避免重复的swap。当然A[i]还要在范围内1 to N
|
t**********h
发帖数: 2273 | 35 public class Solution {
public int firstMissingPositive(int[] a) {
// Start typing your Java solution below
// DO NOT write main() function
if(a == null) return -1;
int n = a.length;
int i = 0;
while(i < n){
if(a[i] != i+1 && a[i] > 0 && a[i] <= n && a[a[i]-1] != a[i]){
swap(a, i, a[i]-1);
}else{
i++;
}
}
for(i = 0; i < n; i++){
if(a[i] != i+1){
return i+1;
}
}
return n+1;
}
private void swap(int[] a, int i, int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
【在 c********p 的大作中提到】
: 求个完整的code我研究研究。。。
|
u*****o
发帖数: 1224 | 36 我记得你用java的。。你看16楼lichen970的代码，第一个就是这个思路写的。
第二个是xor写的。两个写的都很好。这是牛人一枚啊。
【在 c********p 的大作中提到】
: 可是，第一遍的时候，就没有跳回去，然后露掉的么？
: 有完整的代码么？偶来研究一下。
|
c********p
发帖数: 1969 | 37 谢谢，我读读。。。
【在 t**********h 的大作中提到】
: public class Solution {
: public int firstMissingPositive(int[] a) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(a == null) return -1;
: int n = a.length;
:
: int i = 0;
: while(i < n){
: if(a[i] != i+1 && a[i] > 0 && a[i] <= n && a[a[i]-1] != a[i]){
|
c********p
发帖数: 1969 | 38 好的，我去读读。。。
【在 u*****o 的大作中提到】
: 我记得你用java的。。你看16楼lichen970的代码，第一个就是这个思路写的。
: 第二个是xor写的。两个写的都很好。这是牛人一枚啊。
|
s***5
发帖数: 2136 | 39 要sort也是典型的bucket sort，哪用得着O(blog(n))。
于
【在 s*******n 的大作中提到】
: 或者先sort, 再check neighbor的 话， time O(nlogn), Space O(1), 不过都取决于
: sort 的O(sort)
|
t**********h
发帖数: 2273 | 40 我的意思是swap一遍。。。
【在 a********m 的大作中提到】
: 一遍应该不可能。
|
|
|
S*******w
发帖数: 24236 | 41 看看我的code咋样？
【在 c********p 的大作中提到】
: 求个完整的code我研究研究。。。
|
