x****n
发帖数: 74 | 1 不才想请教两道很常见的面试题
（1） 给定array a1,a2,...,an,b1,b2,...,bn，将其变成a1,b1,a2,b2,...,an,bn的
形式
知道有个O(n)解，不过水平比较低，理解起来是在有困难，CareerCup上给了一个
O(nlogn)
的解，不过自己尝试总不能对，希望大牛们指教
（2）另外就是也很常见的在rotated 的sorted的数组里找一个元素的题，是用Binary
search实
现的，但是对于有重复元素的数组就会有错，不知道是不是就不能处理这种情况。
多谢了 | h*******e
发帖数: 225 | 2
O(n)的你就别管了，没有必要。
O(nlogn)的思想是分治。把X=a1,a2...an,b1,b2...bn看作四段A1,A2,B1,B2。假设要求
的置换是F(X), 那么F(X)=F(A1,B1),F(A2,B2), 也就是说，把A2和B1交换，然后递归。
Binary
可以证明，有重复元素的时候，基于比较的算法有O(n)的下界。具体怎么证明你可以想
想。
【在 x****n 的大作中提到】
: 不才想请教两道很常见的面试题
: （1） 给定array a1,a2,...,an,b1,b2,...,bn，将其变成a1,b1,a2,b2,...,an,bn的
: 形式
: 知道有个O(n)解，不过水平比较低，理解起来是在有困难，CareerCup上给了一个
: O(nlogn)
: 的解，不过自己尝试总不能对，希望大牛们指教
: （2）另外就是也很常见的在rotated 的sorted的数组里找一个元素的题，是用Binary
: search实
: 现的，但是对于有重复元素的数组就会有错，不知道是不是就不能处理这种情况。
: 多谢了
| i**********e
发帖数: 1145 | 3 第二题的解答你可以参考这里：
http://ihas1337code.blogspot.com/2010/04/searching-element-in-rotated-array.html
要边看解答边思考，然后自己再写代码，写完后再看解答里面的代码。
Binary
【在 x****n 的大作中提到】
: 不才想请教两道很常见的面试题
: （1） 给定array a1,a2,...,an,b1,b2,...,bn，将其变成a1,b1,a2,b2,...,an,bn的
: 形式
: 知道有个O(n)解，不过水平比较低，理解起来是在有困难，CareerCup上给了一个
: O(nlogn)
: 的解，不过自己尝试总不能对，希望大牛们指教
: （2）另外就是也很常见的在rotated 的sorted的数组里找一个元素的题，是用Binary
: search实
: 现的，但是对于有重复元素的数组就会有错，不知道是不是就不能处理这种情况。
: 多谢了
| m*****g
发帖数: 226 | | i**********e
发帖数: 1145 | 5 有重复的就没办法。
你想一下，binary search 返回找到的值就只有一个，有重复的也只能返回其中一个的
位置。
如果你想找所有重复的位置，那就另当别论，完全是不同的问题了。。。 | x****n
发帖数: 74 | 6 谢谢大侠，我知道分治的方法，但是自己实现总实现不好，主要是在如何分段上出问题
，对于奇数和偶
数长度的分段好像要不同处理，但我的代码始终有Bug，对某个长度的行，对另一个长
度就不行了，很沮
丧。还希望有经验的大牛们指点一二。
【在 h*******e 的大作中提到】
:
: O(n)的你就别管了，没有必要。
: O(nlogn)的思想是分治。把X=a1,a2...an,b1,b2...bn看作四段A1,A2,B1,B2。假设要求
: 的置换是F(X), 那么F(X)=F(A1,B1),F(A2,B2), 也就是说，把A2和B1交换，然后递归。
: Binary
: 可以证明，有重复元素的时候，基于比较的算法有O(n)的下界。具体怎么证明你可以想
: 想。
| x****n
发帖数: 74 | 7 多谢了，我会看看
array.html
【在 i**********e 的大作中提到】
: 第二题的解答你可以参考这里：
: http://ihas1337code.blogspot.com/2010/04/searching-element-in-rotated-array.html
: 要边看解答边思考，然后自己再写代码，写完后再看解答里面的代码。
:
: Binary
| x****n
发帖数: 74 | 8 不是，我不是希望找到所有重复的元素，只是有重复的时候，我判断舍去某一段的逻辑
可能有问题，会
miss
【在 i**********e 的大作中提到】
: 有重复的就没办法。
: 你想一下，binary search 返回找到的值就只有一个，有重复的也只能返回其中一个的
: 位置。
: 如果你想找所有重复的位置，那就另当别论，完全是不同的问题了。。。
| r****o
发帖数: 1950 | 9 这个我也没搞定。感觉好像只有2^N个元素才好用分治。有谁已经搞定了通用的分治算
法吗?
【在 x****n 的大作中提到】
: 谢谢大侠，我知道分治的方法，但是自己实现总实现不好，主要是在如何分段上出问题
: ，对于奇数和偶
: 数长度的分段好像要不同处理，但我的代码始终有Bug，对某个长度的行，对另一个长
: 度就不行了，很沮
: 丧。还希望有经验的大牛们指点一二。
| d****n
发帖数: 233 | 10 Try this:
// Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
algorithm to change
// this array to a1, b1, a2, b2, ..., an, bn.
void Swap(int *A, int i, int j)
{
A[i] ^= A[j];
A[j] ^= A[i];
A[i] ^= A[j];
};
void SwitchOddEven(int *A, int start, int end)
{
if (start >= end)
return;
int mid = (start+end)/2;
// when start = 1, end =4
// then mid = 2, we want left = 2 too, that's why the
// following "+1"
int left = (start + mid + 1
【在 r****o 的大作中提到】
: 这个我也没搞定。感觉好像只有2^N个元素才好用分治。有谁已经搞定了通用的分治算
: 法吗?
| x****n
发帖数: 74 | 11 cool! 没想到这个简洁，多谢大牛指点。
an
【在 d****n 的大作中提到】
: Try this:
: // Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
: algorithm to change
: // this array to a1, b1, a2, b2, ..., an, bn.
: void Swap(int *A, int i, int j)
: {
: A[i] ^= A[j];
: A[j] ^= A[i];
: A[i] ^= A[j];
: };
| h**6
发帖数: 4160 | 12 第一题是完美洗牌问题，可以参考这里的解答：
http://webhome.cs.uvic.ca/~jellis/perfect.html
如果限定O(n)时间，则in place空间没有办法完成，至少需要O(log n)的额外空间。
另：楼上durbin的方法虽然不需要额外空间，但需要O(n logn)的时间。 |
|
