c*********t
发帖数: 2921 | 1 过去这个班上讨论了interleave数组的问题，
给定数组： A B C D E 1 2 3 4 5
输出: A 1 B 2 C 3 D 4 E 5
可是这个问题的对偶题，就是说
给定数组：A 1 B 2 C 3 D 4 E 5
如何in-place把数组变成 A B C D E 1 2 3 4 5
?
谢谢了！ | b******g
发帖数: 1721 | 2 我觉得就是把ABCD变成数字，然后排序。
1. scan array once to find minimum number, min
2. for each character c1, c1 -'A' - min
3. quick sort
O(nlogn) | n*******w
发帖数: 687 | 3 有O（n）解，站内搜索。
【在 b******g 的大作中提到】
: 我觉得就是把ABCD变成数字，然后排序。
: 1. scan array once to find minimum number, min
: 2. for each character c1, c1 -'A' - min
: 3. quick sort
: O(nlogn)
| d*******d
发帖数: 2050 | 4 have fun
void swap_cs(char *a, int i, int j, int n){
for(int k = 0; k
char temp = a[i+k];
a[i+k]=a[j+k];
a[j+k] = temp;
}
return;
}
void switch_string_back(char *a, int i, int j){
if( j-i <=1)
return;
int mid = (i+j)/2;
switch_string_back(a, i, mid);
switch_string_back(a, mid+1, j);
int first_half_mid = (i+mid)/2;
int first_half_n = mid-i+1;
if( first_half_n & 1){
swap_cs(a, first_half_mid+1, j- first_half_n/2 + 1, first_half_n/2);
}else{
swap_cs(a, first_half_mid+1, mid+1, first_half_n/2);
}
return;
} | b******g
发帖数: 1721 | 5 我没搜索，不过我想到了冒泡算法。
因为是interleaving而且字符和数字已经排好序了, 所以就是简单的扫一遍，过程中数
字和后面的字符交换。
准确讲是O(n/2)=>O(n).
【在 n*******w 的大作中提到】
: 有O（n）解，站内搜索。
| r*******g
发帖数: 1335 | 6 难道不是一样采用分枝法？
原题的解答是
A B C D E 1 2 3 4 5 => A B C 1 2 3 D E 4 5 => ....
就是说先交换在分治
你现在这个题的解答是
A 1 B 2 C 3 D 4 E 5 => A B C 1 2 3 D E 4 5 => 。。。。
先分治再交换。
O(n)的算法就算了，nlogn挺好的了。
【在 c*********t 的大作中提到】
: 过去这个班上讨论了interleave数组的问题，
: 给定数组： A B C D E 1 2 3 4 5
: 输出: A 1 B 2 C 3 D 4 E 5
: 可是这个问题的对偶题，就是说
: 给定数组：A 1 B 2 C 3 D 4 E 5
: 如何in-place把数组变成 A B C D E 1 2 3 4 5
: ?
: 谢谢了！
| f*******t
发帖数: 7549 | 7 “过程中数字和后面的字符交换”不是O(n)吧
【在 b******g 的大作中提到】
: 我没搜索，不过我想到了冒泡算法。
: 因为是interleaving而且字符和数字已经排好序了, 所以就是简单的扫一遍，过程中数
: 字和后面的字符交换。
: 准确讲是O(n/2)=>O(n).
| b******g
发帖数: 1721 | 8 提醒的对，我想简单了。那怎么才能O（n）？有没有个大概的思路？我找不到版上的答
案。
【在 f*******t 的大作中提到】
: “过程中数字和后面的字符交换”不是O(n)吧
| r*******g
发帖数: 1335 | 9 我觉得O(nlogn)已经够好了，对于原题，这个版讨论了很多，一个叫shyx(可能记错了)
的id给了个链接上面有O(n)的解答，还用到了素数的东西。
但是这个版面很多人给的O(n)的解答其实不是O(n)，我当时还专门比较过，结果发现基
于分治法的O(nlogn)实际运行起来更快，原因是他们把查找链的过程不算做开销，实际
上这个开销对大的输入是很大的。这个链就是需要交换的位置，一个链的意思就是说上
面的元素依次交换。O(n)的办法无非就是找到这样的多个链。
【在 b******g 的大作中提到】
: 提醒的对，我想简单了。那怎么才能O（n）？有没有个大概的思路？我找不到版上的答
: 案。
| b******g
发帖数: 1721 | 10 学习了。如果还有素数啥的，那我就放弃了。
了)
【在 r*******g 的大作中提到】
: 我觉得O(nlogn)已经够好了，对于原题，这个版讨论了很多，一个叫shyx(可能记错了)
: 的id给了个链接上面有O(n)的解答，还用到了素数的东西。
: 但是这个版面很多人给的O(n)的解答其实不是O(n)，我当时还专门比较过，结果发现基
: 于分治法的O(nlogn)实际运行起来更快，原因是他们把查找链的过程不算做开销，实际
: 上这个开销对大的输入是很大的。这个链就是需要交换的位置，一个链的意思就是说上
: 面的元素依次交换。O(n)的办法无非就是找到这样的多个链。
| d****n
发帖数: 233 | 11 here is a O(nlogn) solution, Rotate can be further optimized.
public class InterleaveShuffle {
public static void main(String argv[]) {
int [] arr = {1,2,3,4,5,100,200,300,400,500};
InplaceInterleave(arr, 0, arr.length - 1);
InplaceRestore(arr, 0, arr.length - 1);
}
static void Reverse(int A[], int left, int right)
{
while (left < right) {
int tmp = A[left];
A[left++] = A[right];
A[right--] = tmp;
}
}
static void Rotate(int A[], int left, int right, int piv) {
if(piv != left){
Reverse(A, left, piv - 1);
Reverse(A, piv, right);
}
Reverse(A, left, right);
}
static void InplaceInterleave(int A[], int left, int right) {
if ((right - left) <= 1) return;
int mid = left + (right - left) / 2;
int halfSize = (right - left + 1) / 2;
int leftMid = left + (mid - left) / 2;
int rightMid = (right + mid + 1) / 2;
Rotate(A, leftMid + 1, rightMid, mid + 1);
InplaceInterleave(A, left, mid + halfSize % 2);
InplaceInterleave(A, mid + 1 + halfSize % 2, right);
}
static void InplaceRestore(int A[], int left, int right) {
if ((right - left) <= 1) return;
int mid = left + (right - left) / 2;
int halfSize = (right - left + 1) / 2;
int leftMid = left + (mid - left) / 2;
int rightMid = (right + mid + 1) / 2;
InplaceRestore(A, left, mid + halfSize % 2);
InplaceRestore(A, mid + halfSize % 2 + 1, right);
Rotate(A, leftMid + 1, rightMid, mid + halfSize % 2 +1);
}
} |
|
