一道微策略面试题
给定一个N个元素的整数，元素分别为A1,A2,A3....AN，将数组变为A1<A2>A3<A4......的锯齿状数组，时间复杂度？
我的思路：先排序，然后再两边向中间取，时间复杂度：O(NlogN),空间复杂度：O(N)。
大家有什么思路啊？
[解决办法]
partition比排序更好点，将数组分为两部分，前半部分的值全部小于后半部分的值
接下来从两个起始位置逐个取数就可以了，
[解决办法]
首先用nth_element把数组划分，以中位数为分界点，所有小于中位数(x)的元素在x之前，大于x的元素在x之后。
然后从两头分别取一个小于x的数，大小x的数，保存到另一数组中。
nth_element的时间复杂度是O(n)的。
例如:
原数组 1 5 3 7 4 2 6
nth_后 1 3 2 4 7 6 5 （只保证4在中间，前三个不一定有序，但都比4小）
新数组 1 7 3 6 2 5 4
#include <iostream>#include <algorithm>using namespace std;int main(){ int a[] = { 1, 5, 3, 7, 4, 2, 6 }; int b[100]; int size = sizeof( a ) / sizeof( a[0] ); int mid = size / 2; nth_element( a, a+mid, a+size ); int index1, index2, index3 = 0; for( index1 = 0, index2 = mid+1; index1 < mid; ++index1, ++index2 ) { b[index3++] = a[index1]; if( index2 < size ) b[index3++] = a[index2]; } b[index3] = a[mid]; for( int i1 = 0; i1 < size; ++i1 ) { cout << b[i1] << " "; } return 0;}