数组题目：求更优解~~~

你的名字 2022-06-13 04:10 132阅读 0赞

给定一个N个元素的整数，元素分别为A1,A2,A3....AN，将数组变为A1<A2>A3<A4......的锯齿状数组，时间复杂度

解：刚刚开始我的想法是，需要把它们先排序，如：1 2 3 4 5 67...然后在进行处理，原理是：首尾保持不变，从第二位和倒数第二位开始交换，然后index(下标)每隔2处理( 即lowIndex += 2；highIndex \-= 2)，结束条件就是 lowIndex>=highIndex；这样其实是可以的，但是大家知道在排序上就有点浪费时间了，后来想了一下没有必要排序的呀，只要保证以中位数为分界点，左边小于分界数，右边大于分界数就可以了，O(∩\_∩)O~，那么代码就easy了~

>>>当然要解决此问题的办法就是首先我们需要转化成这样一个数组：中位数左边的都比它小，右边的都比他大，那么其实我们自己是可以写这个函数的，但是现在STL 中已经有了这样一个函数：[STL样本 nth\_element 函数][STL_ nth_element]！不会的自己看看去呗~O(∩\_∩)O~，其实我们只要调用：nth\_element( a, a + mid, a +allsize )就是可以做到的~ 呵呵，而且 STL 的库函数是有优化的哦，所以还是使用 STL的比较好，函数时间复杂度是O( n ),

主代码：( 仅供参考，人懒没有调试~O(∩\_∩)O~ )（注意：这个参考代码摘自CSDN，非本人写 ）

int main（）

int a\[\] =\{ 1, 5, 3, 7, 4, 2, 6 \};   
    intb\[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( i1 = 0;i1 < size; ++i1 )   
   \{   
       cout << b\[i1\]<< " ";   
   \}

return0;

[STL_ nth_element]: http://support.microsoft.com/kb/158000/zh-cn