leetcode--561--Array Partition I（我的解法）

ゞ浴缸里的玫瑰 2022-06-14 11:38 127阅读 0赞

原题目：

![20170619162632730][]

该题目本质上是先进行升序排序，排序之后从小到大每相邻的两个形成一对，从而sum即为2n个数中的所有奇数位的数之和。具体的证明leetcode上已经有大神证明这种方法会使得目标函数达到最优。

我的解法:

![20170619164534225][]

这个解法我经过自己测试是正确的，但是在leetcode上提交之后是错误的，显示time limit exceeded，查了一下，出现这个错误的原因主要有两种，一个是出现死循环，一个是算法复杂度过高。我的问题应该是我用了最简单的排序算法，因此导致算法复杂度过高，所以还是调用c++封装后的库函数sort函数吧：（以后记住，最简单的升序排序方法就用sort函数吧）

![20170619164545358][]

sort函数用法总结:

template <class RandomAccessIterator>//模板1
    
     void sort ( RandomAccessIterator first, RandomAccessIterator last );
     
    template <class RandomAccessIterator, class Compare>//模板2
     void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

使用模板1是对\[first,last)进行升序排序，默认操作符为"<"。

模板2中使用comp函数进行排序控制，comp包含两个在\[first,last)中对应的值，如果使用"<"则为升序排序，如果使用">"则为降序排序

sort是STL中提供的函数，头文件为\#include<algorithm>以及using namespace std

下面是一个数组实例:

int a[5]={4,1,2,6,8};
    sort(a,a+5);

我的解法中，为vector型数组，因此使用的是begin函数和end函数。begin返回的是容器的第一个元素，end返回的是最后一个元素的下一个，也就不是容器中的元素。

[20170619162632730]: /images/20220614/e967f167bb634117b41d552282183f51.png
[20170619164534225]: /images/20220614/a4a2c2f673f84d40bef7e76c90854721.png
[20170619164545358]: /images/20220614/8a941d97c66a4a4e8b25945bc7767ed0.png