題目鏈接：點(diǎn)擊查看

題目大意：現(xiàn)在給出n*(n-1)/2個關(guān)系表示n個數(shù)中兩兩之間的關(guān)系大小，用函數(shù)表示就是compare(a,b)，若a<b，則返回值為true，否則返回值為false，要求我們編寫一個類用來還原數(shù)組，并要求最多訪問10*N次compare函數(shù)

題目分析：時間復(fù)雜度既然要求了10*N，那么首先就要想到nlogn，這個題目中的n給到了1e3，logn不超過10，所以滿足時間復(fù)雜度的要求，現(xiàn)在我們就要想該怎么實現(xiàn)

要是用sort直接排序的話會被卡掉，因為sort是不穩(wěn)定排序，也就是重復(fù)元素也有可能會互換位置，最壞的時間復(fù)雜度能到n*n的級別，肯定不滿足這個題目，但我們可以用歸并排序，歸并排序最大的一個特點(diǎn)就是穩(wěn)定，時間復(fù)雜度穩(wěn)定在nlogn，完美契合這個題目，而且也是屬于C++內(nèi)置的函數(shù)stable_sort()，用法和sort一樣，我也是今天才知道的。。

當(dāng)然正解應(yīng)該是二分來做的。。因為logn的時間復(fù)雜度也可以聯(lián)想到二分，對于每一個數(shù)字二分查找所在的位置，然后直接用vector的insert函數(shù)插入就好了，也是學(xué)了一波insert函數(shù)，這個函數(shù)有兩個參數(shù)，分別是pos和val，功能是將val插入到pos位置前面

這個題真的學(xué)到了不少小細(xì)節(jié)。。

代碼：

歸并排序：

// Forward declaration of compare API. // bool compare(int a, int b); // return bool means whether a is less than b.class Solution { public:vector<int> specialSort(int N) {vector<int>ans;for(int i=1;i<=N;i++)ans.push_back(i);stable_sort(ans.begin(),ans.end(),compare);return ans;} };

二分：

// Forward declaration of compare API. // bool compare(int a, int b); // return bool means whether a is less than b.class Solution { public:vector<int> specialSort(int N) {vector<int>ans;ans.push_back(1);for(int i=2;i<=N;i++){int l=0,r=ans.size()-1;int pos=r+1;//注意pos初始化為r+1，因為最壞情況是當(dāng)前的i是最大值，應(yīng)該放在最后面while(l<=r){int mid=(l+r)>>1;if(compare(i,ans[mid])){pos=mid;r=mid-1;}elsel=mid+1;}ans.insert(ans.begin()+pos,i);}return ans;} };

?

總結(jié)

以上是生活随笔為你收集整理的AcWing - 113 特殊排序(归并排序/二分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。