|
|---|
|
| 相关主题 |
|---|
| ● stable rearrange an integer array with + and - | ● Quick Sort的partition问题 | | ● MS a0, a1, ..., b0, b1... 问题 | ● leetcode Palindrome Partitioning | | ● 关于2D, 3D平面上点的问题？ | ● 一个容易记忆的permutation算法 | | ● 问个Array Puzzle题 | ● 那个常见的histogram max rectangle 问题 | | ● The time complexity on finding the kth largest element in a | ● 问个google面试题 | | ● array a1,a2,... ,an, b1,b2,..., bn | ● 请问G一题 | | ● partition array problem | ● 怎么理解递归解决的“swap every two elements in a linked list”？ | | ● string scramble 的时间复杂度 | ● 问题：Find the minimum number of "swaps" needed to sort an array |
|
|
|
|
|
h********0
发帖数: 440 | 1 given an array with data like: a1 a2... an b1 b2 ...bn
Change the array to a1 b1 a2 b2 ... an bn
看到career cup上这个题目可以用divide and conquer，但是那个exchange的部分我
test了几个情况，好像都有问
题。
Rough idea:
find the middle index r = floor((p+q)/2)
It partitions the array to part 1 [p, r] and part2 [r+1, q]
then exchange the second half of part [(p+r)/2...r] and the first half of
part 2 [r+1, (r+q)/2]
recursively call this function.
Initially, call this function func(p,q) use parameters p=1,q=2n
Test case 1: a1 a2 a3 a | r**u
发帖数: 1567 | 2 这题已经被讨论好多遍了，结论是不用extra space只能O(n^2)。
【在 h********0 的大作中提到】
: given an array with data like: a1 a2... an b1 b2 ...bn
: Change the array to a1 b1 a2 b2 ... an bn
: 看到career cup上这个题目可以用divide and conquer，但是那个exchange的部分我
: test了几个情况，好像都有问
: 题。
: Rough idea:
: find the middle index r = floor((p+q)/2)
: It partitions the array to part 1 [p, r] and part2 [r+1, q]
: then exchange the second half of part [(p+r)/2...r] and the first half of
: part 2 [r+1, (r+q)/2]
| S******A
发帖数: 1002 | 3 交换[(n-1)/2, n-1] and [n, n+(n-1)/2] | h********0
发帖数: 440 | 4 我知道这个可能被讨论很多遍了，我现在想了解的是如果用这个
divide and conquer 的解决办法，有没有什么更好的方式解决这个recursion的问题。
【在 r**u 的大作中提到】
: 这题已经被讨论好多遍了，结论是不用extra space只能O(n^2)。
| B*****t
发帖数: 335 | 5 there is a paper on how to do it in O(N) without extra space. But need some
mathematical results from number theory.
Maybe I am wrong, not very clear.
but it can be done in O(NlogN)
【在 r**u 的大作中提到】
: 这题已经被讨论好多遍了，结论是不用extra space只能O(n^2)。
| h********0
发帖数: 440 | 6 you can try it using the above test cases, it does not work.
【在 S******A 的大作中提到】
: 交换[(n-1)/2, n-1] and [n, n+(n-1)/2]
| h********0
发帖数: 440 | 7 Thought of a naive change, but the code is not pretty.
Basically, this recursion is a problem for partitions with odd numbers.
We can do a preprocess after partition.
1. if the two parts contain even number,no change.
2. if the two parts contain odd number,
do the following ugly exchange
part 1: [p...r]
part 2: [r+1 ...q]
logically:
exchange the right half of part 1 and the left half of part 2
move the middle element of part 1 to array[r]
move the middle element of part
【在 h********0 的大作中提到】
: given an array with data like: a1 a2... an b1 b2 ...bn
: Change the array to a1 b1 a2 b2 ... an bn
: 看到career cup上这个题目可以用divide and conquer，但是那个exchange的部分我
: test了几个情况，好像都有问
: 题。
: Rough idea:
: find the middle index r = floor((p+q)/2)
: It partitions the array to part 1 [p, r] and part2 [r+1, q]
: then exchange the second half of part [(p+r)/2...r] and the first half of
: part 2 [r+1, (r+q)/2]
| b**f
发帖数: 20 | | r****o
发帖数: 1950 | 9 我也想过这个问题，感觉如果2n是2的几次方的话，用divide and conquer 好做。
否则好像很麻烦。
【在 h********0 的大作中提到】
: given an array with data like: a1 a2... an b1 b2 ...bn
: Change the array to a1 b1 a2 b2 ... an bn
: 看到career cup上这个题目可以用divide and conquer，但是那个exchange的部分我
: test了几个情况，好像都有问
: 题。
: Rough idea:
: find the middle index r = floor((p+q)/2)
: It partitions the array to part 1 [p, r] and part2 [r+1, q]
: then exchange the second half of part [(p+r)/2...r] and the first half of
: part 2 [r+1, (r+q)/2]
| f**r
发帖数: 865 | 10 The divide & conquer algorithm is nlog(n) ah, N elements swapped in each
round, logn rounds in total. | r****o
发帖数: 1950 | 11 能不能说说如果2*n不是2的几次方(如4,8,16...)的话，用divide and conquer怎么作？
【在 f**r 的大作中提到】
: The divide & conquer algorithm is nlog(n) ah, N elements swapped in each
: round, logn rounds in total.
| r****o
发帖数: 1950 | 12 请问不用extra space 是什么意思啊？
临时变量行不？
能不能说说你的O(n^2)的思路？
【在 r**u 的大作中提到】
: 这题已经被讨论好多遍了，结论是不用extra space只能O(n^2)。
| f**r
发帖数: 865 | 13 One final pass for the remaining numbers. Example:
a1 a2 a3 a4 a5 a6
b1 b2 b3 b4 b5 b6
=>
a1 b1 a3 b3 a5 b5
a2 b2 a4 b4 a6 b6
=>
a1 b1 a2 b2 a5 b5
a3 b3 a4 b4 a6 b6
Now we would like to switch (a5, b5) (incomplete) with (a3, b3, a4, b4).
Here, the problem is equivalent to left shift subarray {a5 b5 a3 b3 a4 b4}
by 2, another interview question that has an O(N) solution. :-)
作？
【在 r****o 的大作中提到】
: 能不能说说如果2*n不是2的几次方(如4,8,16...)的话，用divide and conquer怎么作？
| d********e
发帖数: 132 | 14 In-Place Algorithm for In-Shuffle
http://arxiv.org/abs/0805.1598 |
|
|
|
|
| 相关主题 |
|---|
| ● 问题：Find the minimum number of "swaps" needed to sort an array | ● The time complexity on finding the kth largest element in a | | ● 再论 mini # of swaps to sort array. | ● array a1,a2,... ,an, b1,b2,..., bn | | ● minMSwap 这题能比O(n^2)更快的解法吗 | ● partition array problem | | ● 问一问这个题。 | ● string scramble 的时间复杂度 | | ● stable rearrange an integer array with + and - | ● Quick Sort的partition问题 | | ● MS a0, a1, ..., b0, b1... 问题 | ● leetcode Palindrome Partitioning | | ● 关于2D, 3D平面上点的问题？ | ● 一个容易记忆的permutation算法 | | ● 问个Array Puzzle题 | ● 那个常见的histogram max rectangle 问题 |
|
|
|
