數據范圍是3500,3500也就是說n的平方是可以接受的。這里告訴你就是有序的,也就是在提醒你可能會是一個類似于二分的算法,所以的話其實基于這兩個認識的話我們就可以利用一個枚舉叫二分的算法來解決這道題。怎么做呢？就首先的話我們要枚舉一端,一端的話我們可以把所有的這個lists的里面所有元素都給去重然后對它進行左端的一個枚舉,然后右端的話的呢我們就分別對每一個list進行一個二分來查找它可能包含所有至少來查找這個至少包含一個元素的最大的這么一個區(qū)間是什么。然后我們每次枚舉的時候把這些最大的區(qū)間找一個最小的出來,這就是我們所需要的一個答案。那么這個整個復雜度的話應該是k的平方乘以一個log所有l(wèi)ists里面最大的一個,所有l(wèi)ists里面一個最長的元素n,所以應該是k^2*logn,這個復雜度是可以接受的。

首先呢是要對這個我們要對就要枚舉的這個元素進行去重,這樣我們就可以減少這個運算量。這里呢我用一種可能大家不怎么熟悉的一種去重的方法,就是用一個sort+unqiue這個方法來進行去重。然后unique的話呢是用于一個有序的數組的一個去重的方法。然后unique它返回的這個東西的下標,就最后一個元素的下標。然后注意的話這個unique的話,也就是對有序的、就是已經排好序的這么一個數組才能進行去重,不然的話它就有可能返回一個錯誤的結果。

?

這樣我們就得到了它在已經去重之后的這個vi的區(qū)間是在哪兒,所以的話我們就可以來進行枚舉了。枚舉的話呢我們就直接就遍歷到offset就行。offset是去重之后的vi的區(qū)間。注意一下這個unique去重之后是一個左閉右開的一個區(qū)間,就是STL的一個慣例。然后的話我們這個區(qū)間我們還得定義一下這個區(qū)間的話可能那個最大值就是是多少,我們最大值肯定是排完序之后的,左邊的話它肯定是它的那個最小值,所以我們這邊就直接用這個排好序之后的一個最小值以及排好序之后的最大值,就這里減1,因為是左閉右開。然后這里應該是枚舉的話我們先把這個區(qū)間鎖定在一個秩上面,最后我們來進行一個擴展,然后之后再跟大L、跟大R進行比較。然后我們有時候的話我們可能枚舉的話可能是找不到一個合適的值,比如說我們如果是拿26去枚舉的話,我們就肯定就,20、26作為它的那個左邊那個值的話是肯定得不到一個正確的值的。比如說26到哪兒都,到30的話肯定是覆蓋不了所有的區(qū)間的,所以的話那我們要定義一個布爾變量來判斷一下我們是否是不是能找到這個值,所以的話我們就開始遍歷所有的vector,然后的話,我們這里要用lower_bound,就是說找到第一個出現、第一次出現的地方,這樣的話才是我們所需要的那個最小的區(qū)間。因為的話我們每次枚舉的話肯定都是要找一個最大符合的,我們不是找最小符合的,就最小符合的話可能就其它區(qū)間就不會滿足了,這樣的話我們才有機會覆蓋所有的,就我們以l這個值為枚舉的話,我們才有可能找到這個r,l到r的話可以覆蓋所有的這個區(qū)間。

?

class Solution { public:vector<int> smallestRange(vector<vector<int>>& nums) {//sort+unique [1,1,1,2,3,3]->[1,2,3,XXXXXX]//vector<int> vi,rt;vector<int> vi;for (auto& i:nums) {for (auto j:i) {vi.push_back(j); }}sort(vi.begin(), vi.end());//vector<int>::iterator offset= unique(vi.begin(),vi.end());int L = *vi.begin();//int R = *vi.end()-1;int R = *(vi.end() - 1);int offset = unique(vi.begin(), vi.end()) - vi.begin();for (int i = 0;i < offset;i++) {int l = vi[i];int r = vi[i];bool find = false;for (auto& j : nums) {auto iter = lower_bound(j.begin(),j.end(),l);if (iter != j.end()) {find = true;r = max(*iter,r);}else {find = false;break;}}if (find) {if ((r -l<R-L)||(l<L&&r-l==R-L)) {L = l;R = r;}}}//rt.push_back(vi[L]);//rt.push_back(vi[R]);//return rt;return { L,R };} };

?

轉載于:https://www.cnblogs.com/ZHONGZHENHUA/p/10781087.html

總結

以上是生活随笔為你收集整理的LeetCode Smallest Range的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。