B*******1
发帖数: 2454 | 1 Given an integer array of which both first half and second half are sorted.
Write a function to merge the two parts to create one single sorted array in
place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2
,1,3,3,6,8,8]
似乎以前在这里见过，现在找不到那个帖子了，这题最佳算法是什么啊。 | f*******t
发帖数: 7549 | 2 搜下in place merge sort
这个题只要merge部分 | b*******y
发帖数: 232 | 3 需不需要用到 At*Bt = (BA)t t= transpose？
【在 f*******t 的大作中提到】
: 搜下in place merge sort
: 这个题只要merge部分
| B*******1
发帖数: 2454 | 4 大侠，搜索了一下，没有找到，可以指点一下吗。
【在 f*******t 的大作中提到】
: 搜下in place merge sort
: 这个题只要merge部分
| b*****1
发帖数: 52 | 5 search each element of the 1st half of array in the 2nd half of the array,
and then rotate the elements before that position, repeat until reach the
end of the array. O(nlogn) time and in-place. | J*********n
发帖数: 370 | 6
how to rotate? did you mean shift the elements in the 2nd half by one
position? if so, it's O(n^2), not O(nlogn)
【在 b*****1 的大作中提到】
: search each element of the 1st half of array in the 2nd half of the array,
: and then rotate the elements before that position, repeat until reach the
: end of the array. O(nlogn) time and in-place.
| A**u
发帖数: 2458 | 7 这么实现就可以了
我也新手，不会写算法
1 3 6 8 -5 -2 3 8
1. 判断 A[i+1] < A[i], 如果yes, A[i]就是 前半段最后一个， A[i+1] 就是后半段
第一个
2. i = 0; j = k; i,j 分别指向1st,2nd part.
3. 判断 A[i] < A[k],
小于，则不动， i++
大于，交换 A[i],A[k] (-5 3 6 8 1 -2 3 8), 接着 A[k] 比较 A[k+1],放到合
适位置，成为 (-5 3 6 8 -2 1 3 8). i++
4 继续
(-5 -2 6 8 3 1 3 8)...(-5 -2 6 8 1 3 3 8).
(-5 -2 1 8 6 3 3 8) ... (-5 -2 1 8 3 3 6 8)
(-5 -2 1 3 8 3 6 8) .... (-5 -2 1 3 3 6 8 8 )
.
in
-2
【在 B*******1 的大作中提到】
: Given an integer array of which both first half and second half are sorted.
: Write a function to merge the two parts to create one single sorted array in
: place [do not use any extra space].
: e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2
: ,1,3,3,6,8,8]
: 似乎以前在这里见过，现在找不到那个帖子了，这题最佳算法是什么啊。
| C*******l
发帖数: 1198 | 8 这个是类似那个将 a1 a3 ... an an+1 an+2 ... a2n-1 a2n 排成 a1 a2 ... an ...
a2n 的题目。我只懂用insertion。但因为要每次都search半个array，间中还会转移
pivot，所以是 T(n) = n * 2 * lg(n/2) + n = O(n lg n)。 | b*****1
发帖数: 52 | 9 rotate from the current searched element to the found position in the 2nd
half element. The total number of rotation will be no more than n. The
search is logn. So the total complexity is O(nlogn)
1,3,6,8,-5,-2,3,8
#1 search a[0]=1 between i=4 to 7: found 1 before i=6, rotate the array
before i=6:
-5 -2 1 3 6 8 3 8
#2 search a[3]=3 between i=6 to 7: found 3 before i=7, roate the array
between i=3 (current search position) and i=7 (found position)
-5 -2 1 3 3 6 8 8
#3 search a[5]=6 between i=7 to 7: not found, don't rotate
# end of array, done
//code
void Merge( int a[], int n) {
if(n<=2) return;
int cur=0, curLen=n/2;
int pos = found(a, a[cur], n/2, n) // binary search of a[cur] in a[]
between i=n/2 and n;
while(pos0) {
rotate( a, cur, pos, pos-cur-curLen); // rotate a between position cur
and pos for pos-cur-curLen items.
cur = cur+pos-curLen;
--curLen;
pos = found(a, a[cur], pos, n);
}
return;
}
【在 J*********n 的大作中提到】
:
: how to rotate? did you mean shift the elements in the 2nd half by one
: position? if so, it's O(n^2), not O(nlogn)
| l*********y
发帖数: 142 | 10 Hi breeze1,
没看懂你的算法，请问rotate怎么会是O（1）哪？
【在 b*****1 的大作中提到】
: rotate from the current searched element to the found position in the 2nd
: half element. The total number of rotation will be no more than n. The
: search is logn. So the total complexity is O(nlogn)
: 1,3,6,8,-5,-2,3,8
: #1 search a[0]=1 between i=4 to 7: found 1 before i=6, rotate the array
: before i=6:
: -5 -2 1 3 6 8 3 8
: #2 search a[3]=3 between i=6 to 7: found 3 before i=7, roate the array
: between i=3 (current search position) and i=7 (found position)
: -5 -2 1 3 3 6 8 8
| l********g
发帖数: 24 | 11 "The total number of rotation will be no more than n."
觉得不对.
在把1,3,6,8,-5,-2 rotate 成 -5,-2,1,3,6,8时,就需要swap 6组数字。rotate的
cost是O(k),k是需要rotate部分的长度。
In worst case, 每次rotate后,下一次需要rotate的部分长度减1
1,3,5,7,2,4,6,8
1. rotate (1,3,5,7,2)
--> 1,2, 3,5,7,4,6,8
2. rotate (3,5,7,4)
--> 1,2,3,4,5,7,6,8
3. rotate (5,7,6)
---> 1,2,3,4,5,6,7,8
O(N/2+1)+O(N/2)+O(N/2-1)+O(N/2-2)+... until O(1)
The sum above should be O(N*2)
我想到的算法也是这样rotate，但是时间我觉得是O(N*2).有更快的么？ |
|
