r*******o
发帖数: 62 | 1 问题就是 把这个数组 a1a2a3a4b1b2b3b4 弄成这样子 a1b1a2b2a3b3a4b4
in place , O(1) space complexity
我看了好多讨论里面 都直接略去了time O(n^2) 的这种方法 我面试的时候想了半天
连这个n方的方法都没想出来 弱归弱 希望有牛人给出一个N^2的解法 感激不尽！ |
o***i
发帖数: 603 | 2 public void Swap(k[] ks){
int m = ks.length/2;
for (int i = 1; i < m; i++) {
for (int j = 0; i+j < m; j++) {
swap(i+j, m+j, ks);
}
}
}
private void swap(int a, int b, K[] arr) {
K m;
m = arr[b];
arr[b] = arr[a];
arr[a] = m;
}
【在 r*******o 的大作中提到】
: 问题就是 把这个数组 a1a2a3a4b1b2b3b4 弄成这样子 a1b1a2b2a3b3a4b4
: in place , O(1) space complexity
: 我看了好多讨论里面 都直接略去了time O(n^2) 的这种方法 我面试的时候想了半天
: 连这个n方的方法都没想出来 弱归弱 希望有牛人给出一个N^2的解法 感激不尽！
|
A**u
发帖数: 2458 | |
w***y
发帖数: 6251 | 4 感觉要求是[i,i+1]两个两个一起读， 先按[i+1]的值比大小／再按[i]比大小？
如果这样的话， inplace排序方法都可以用上， 就是code起来复杂的多 |
s***5
发帖数: 2136 | 5 N^2的方法都想不出？太离谱了，用你的intuition就行了。 |
s*******s
发帖数: 1031 | 6 有没有比n^2更好的办法？
我想破了头都没有办法。 :(
【在 s***5 的大作中提到】
: N^2的方法都想不出？太离谱了，用你的intuition就行了。
|
o***i
发帖数: 603 | 7 能O(N)的，按照一定的顺序替换，貌似有论文的
面试时要求做出O(N)的话那只能说太BT了
【在 s*******s 的大作中提到】
: 有没有比n^2更好的办法？
: 我想破了头都没有办法。 :(
|
r*******o
发帖数: 62 | 8 非常非常感谢 终于被我看明白咋回事了
【在 o***i 的大作中提到】
: public void Swap(k[] ks){
: int m = ks.length/2;
:
: for (int i = 1; i < m; i++) {
: for (int j = 0; i+j < m; j++) {
: swap(i+j, m+j, ks);
: }
: }
:
: }
|
r*******o
发帖数: 62 | 9 我理解了一下N^2的方法 看来是我的思维太局限了 不过能想出来的人我都觉得很厉
害
【在 A**u 的大作中提到】
: 这题不简单啊
|
r*******o
发帖数: 62 | 10 额…… 貌似没怎么看明白你的重点 我找了几个方法看了一下 简单到困难 发现都挺
巧妙的
【在 w***y 的大作中提到】
: 感觉要求是[i,i+1]两个两个一起读， 先按[i+1]的值比大小／再按[i]比大小？
: 如果这样的话， inplace排序方法都可以用上， 就是code起来复杂的多
|
|
|
r*******o
发帖数: 62 | 11 没想到这种分块的操作 确实也是训练不够
【在 s***5 的大作中提到】
: N^2的方法都想不出？太离谱了，用你的intuition就行了。
|
r*******o
发帖数: 62 | 12 我也看了一下 有O(n)的方法 设计很巧妙 而且还需要一个数学的定理
【在 s*******s 的大作中提到】
: 有没有比n^2更好的办法？
: 我想破了头都没有办法。 :(
|
l*n
发帖数: 529 | 13 从递归的角度看比较好理解，a1(a1a3)b1(b2b3)=>a1b1(a2a3)(b2b3)，然后用循环搞定
递归就满足space O(1)了。 |
b****g
发帖数: 192 | 14 其实O(n^2)的方法应该读完题就瞬间想到了，因为太intuitive了基本就不是算法，
LZ估计是面试时稍有紧张于是不易思考了。我面试时也是，可是放下电话一瞬间就全都
想出来了。
【在 r*******o 的大作中提到】
: 问题就是 把这个数组 a1a2a3a4b1b2b3b4 弄成这样子 a1b1a2b2a3b3a4b4
: in place , O(1) space complexity
: 我看了好多讨论里面 都直接略去了time O(n^2) 的这种方法 我面试的时候想了半天
: 连这个n方的方法都没想出来 弱归弱 希望有牛人给出一个N^2的解法 感激不尽！
|
w***y
发帖数: 6251 | 15 可能我想的太简单了，我的感觉就是自己定一个 ‘比较’函数－－ 一般的sorting不
就是直接比大小，这个‘compare’是判断 a1 < b1, a1
【在 r*******o 的大作中提到】
: 额…… 貌似没怎么看明白你的重点 我找了几个方法看了一下 简单到困难 发现都挺
: 巧妙的
|
r*******o
发帖数: 62 | 16 这个方法和2楼给出的不一样 而且竟然这么简单 没想出来还是我自己太弱了
【在 l*n 的大作中提到】
: 从递归的角度看比较好理解，a1(a1a3)b1(b2b3)=>a1b1(a2a3)(b2b3)，然后用循环搞定
: 递归就满足space O(1)了。
|
r*******o
发帖数: 62 | 17 要是非得找点理由 我觉得差不多 刚刚看了你楼上的分析 突然觉得这么弱的东西都
没想出来 面试官肯定觉得我的思路太狭窄了
【在 b****g 的大作中提到】
: 其实O(n^2)的方法应该读完题就瞬间想到了，因为太intuitive了基本就不是算法，
: LZ估计是面试时稍有紧张于是不易思考了。我面试时也是，可是放下电话一瞬间就全都
: 想出来了。
|
r*******o
发帖数: 62 | 18 因为数组里面可能是任意数字 举个例子 a1=10 a2=15 b1=2 b2= 2 所以我个人觉得
只是通过数字本身没法定义到底谁大谁小
【在 w***y 的大作中提到】
: 可能我想的太简单了，我的感觉就是自己定一个 ‘比较’函数－－ 一般的sorting不
: 就是直接比大小，这个‘compare’是判断 a1 < b1, a1
|
w***y
发帖数: 6251 | 19 ic. 我完全领悟错了
【在 r*******o 的大作中提到】
: 因为数组里面可能是任意数字 举个例子 a1=10 a2=15 b1=2 b2= 2 所以我个人觉得
: 只是通过数字本身没法定义到底谁大谁小
|
s*****n
发帖数: 5488 | 20 这题虽然忘了解法，不过顺着当年依稀的记忆写个不是0(n^2)的算法吧。
int shuffle(int[] arr, int n){
assert(n%2 == 0);
if (n <=2)
return;
for (int i = n/4; i < n/2; i--)
swap(arr, i, i + n/2);
shuffle(arr,0, n/2);
shuffle (arr, n/2, n);
}
【在 r*******o 的大作中提到】
: 问题就是 把这个数组 a1a2a3a4b1b2b3b4 弄成这样子 a1b1a2b2a3b3a4b4
: in place , O(1) space complexity
: 我看了好多讨论里面 都直接略去了time O(n^2) 的这种方法 我面试的时候想了半天
: 连这个n方的方法都没想出来 弱归弱 希望有牛人给出一个N^2的解法 感激不尽！
|
x*****0
发帖数: 452 | |
