w********8
发帖数: 55 | 1 数组排序， 排成 a1a3a5。。。这种形式。
想了半天，没想到比O(n^2)更好的算法。
请教大牛们。 |
l*********8
发帖数: 4642 | 2 两两比较相邻数字，把大的数字放到下标为奇数的位置。 O(n)
【在 w********8 的大作中提到】
: 数组排序， 排成 a1a3a5。。。这种形式。
: 想了半天，没想到比O(n^2)更好的算法。
: 请教大牛们。
|
y**********a
发帖数: 824 | 3 O(nlog n)
把临近的奇数换到偶数(index)上
void weirdSort(int[]A) {
assert((A.length&1)==1);
Arrays.sort(A);
for (int i=1;i+1
{A[i]^=A[i+1];A[i+1]^=A[i];A[i]^=A[i+1];}
} |
w********8
发帖数: 55 | 4
原来如此，谢谢楼上二位！
【在 y**********a 的大作中提到】
: O(nlog n)
: 把临近的奇数换到偶数(index)上
: void weirdSort(int[]A) {
: assert((A.length&1)==1);
: Arrays.sort(A);
: for (int i=1;i+1: {A[i]^=A[i+1];A[i+1]^=A[i];A[i]^=A[i+1];}
: }
|
w********8
发帖数: 55 | 5 这个O(n)的算法更好一点。
谢谢！
【在 l*********8 的大作中提到】
: 两两比较相邻数字，把大的数字放到下标为奇数的位置。 O(n)
|
p********n
发帖数: 165 | 6 先排序就得nlogn
然后再比较奇偶 n
所以总体还是O(nlogn) |
l*********b
发帖数: 65 | 7 其实不用奇偶吧 只要两两比较数字 把不满足要求的 和下一个数字对调 就好啦。
比如 7,8 。7的位置应该是大数， 但是它又比8小 所以就和8调换 这样变成 8,7。 就
一定满足啦 因为8肯定是因为比7大才被调换的 所以一定也比7前面的数字大。
说得不太清楚 试一下就好啦。 |
p********n
发帖数: 165 | 8 5< 6 > 2 < 3 前4个数字都是对的， 突然第五个数字出现个1000 你怎么对调？怎么
保证O(n)? |
s*********s
发帖数: 5 | 9 O(N)可解
A[i]为当前考察对象，假设
当i是奇数时，如果A[i]
当i是偶数时，如果A[i]>A[i+1] 则swap(A[i], A[i+1])
5< 6 > 2 < 3 前4个数字都是对的， 突然第五个数字出现个1000 你怎么对调？
只需要将3和1000交换即可 |
s*******7
发帖数: 23 | 10 我觉得O(n) 可以做
1. 把无序的array给heapify
2. 建立binary tree， 建的方法是 Ai 的左边 是 A（2i＋1）， 右边子节点是 A（
2i ＋ 2）
3. 把这个树， inorder打印就行了
泡这个版多年， 作点贡献 ：） |
A****0
发帖数: 1073 | 11 这题我感觉有个陷阱——Duplicates，当duplicate数超过数组长度一半时无解。
而且有duplicate时只有sort的办法最好，其他好些办法都不行。 |
w********8
发帖数: 55 | 12 没错，非常好的分析！
面试时候要注意到。
谢谢
【在 A****0 的大作中提到】
: 这题我感觉有个陷阱——Duplicates，当duplicate数超过数组长度一半时无解。
: 而且有duplicate时只有sort的办法最好，其他好些办法都不行。
|
B********4
发帖数: 7156 | 13 这题有个不清楚的地方，比如a1和a3的关系怎样？必须a1
如果a1
【在 w********8 的大作中提到】
: 数组排序， 排成 a1a3a5。。。这种形式。
: 想了半天，没想到比O(n^2)更好的算法。
: 请教大牛们。
|
