【分治アルゴリズム】Leetcodeプログラミング問題解:493.Reverse Pairs Add to List
2489 ワード
タイトル:
Given an array
You need to return the number of important reverse pairs in the given array.
サンプル:
1.
Input: [1,3,2,3,1]
Output: 2
2.
Input: [2,4,3,5,1]
Output: 3
要件: The length of the given array will not exceed All the numbers in the input array are in the range of 32-bit integer.
タイトルはちょうど二分検索で解決して、先に1つの新しい配列を申請してそのすべての値の2倍を保存して、並べ替えて、それから毎回元の配列の中の値を取って中間値として探して、コードは以下の通りです:
ただし、タイムアウトしたため、通過したコードを参照して、集計ソートで解決します.以下は抜粋です.
Just a mergesort solution, but using iterators (instead of indexes) and
Given an array
nums
, we call (i, j)
an important reverse pair if i < j
and nums[i] > 2*nums[j]
. You need to return the number of important reverse pairs in the given array.
サンプル:
1.
Input: [1,3,2,3,1]
Output: 2
2.
Input: [2,4,3,5,1]
Output: 3
要件:
50,000
. タイトルはちょうど二分検索で解決して、先に1つの新しい配列を申請してそのすべての値の2倍を保存して、並べ替えて、それから毎回元の配列の中の値を取って中間値として探して、コードは以下の通りです:
class Solution {
public:
vector::iterator find(vector& tmp,long aim)
{
int a=0,b=tmp.size()-1;
while(aaim)
b=c-1;
else if(tmp[c]& tmp,int a)
{
int begin=0,end=tmp.size()-1,middle;
if(end<0)
return 0;
while(begin=a)
return begin;
else
return tmp.size();
}
int reversePairs(vector& nums) {
int n=nums.size();
vectortmp(n,0);
for(int i=0;i::iterator iter=find(tmp,aim);
tmp.erase(iter);
ans+=count(tmp,nums[i]);
}
return ans;
}
};
ただし、タイムアウトしたため、通過したコードを参照して、集計ソートで解決します.以下は抜粋です.
Just a mergesort solution, but using iterators (instead of indexes) and
inplace_merge
. class Solution {
public:
int sort_and_count(vector::iterator begin, vector::iterator end) {
if (end - begin <= 1)
return 0;
auto mid = begin + (end - begin) / 2;
int count = sort_and_count(begin, mid) + sort_and_count(mid, end);
for (auto i = begin, j = mid; i != mid; ++i) {
while (j != end and *i > 2L * *j)
++j;
count += j - mid;
}
inplace_merge(begin, mid, end);
return count;
}
int reversePairs(vector& nums) {
return sort_and_count(nums.begin(), nums.end());
}
};