Problem:
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.
Example1:
Input: [1,3,2,3,1]Output: 2
Example2:
Input: [2,4,3,5,1]Output: 3
Note:
- The length of the given array will not exceed
50,000. - All the numbers in the input array are in the range of 32-bit integer.
Solution:
这道题再用类似中的插入排序方法就只能打擦边球AC了，类似的，这道题应该要想到用来解决。我们用一个集合s存储所有不重复的数字，然后用一个sorted数组存储排序后的唯一的数字，用一个哈希表记录了唯一的数字对应的rank值，并维护了一个FenwickTree，用rank数组对所有数字进行一个排名。和Leetcode 315类似，我们需要在这个树状数组中寻找前x个数之和，不同的是，Leetcode 315的处理比较简单，这里的x是比nums[i]/2.0小的最大值，我们可以利用这个sorted数组进行二分查找。然后不断更新这个树状数组即可。时间复杂度是O(nlogn)
Code:
1 class FenwickTree{ 2 public: 3 FenwickTree(int N){ 4 data = vector (N+1); 5 tree = vector (N+1); 6 } 7 void update(int index){ 8 for(int i = index;i < tree.size();i+=lowBit(i)) 9 tree[i] += 1;10 data[index]++;11 }12 int getSum(int last){13 int result = 0;14 for(int i = last;i > 0;i-=lowBit(i))15 result += tree[i];16 return result;17 }18 private:19 int lowBit(int x){20 return x&(-x);21 }22 vector tree;23 vector data;24 };25 26 class Solution {27 public:28 int reversePairs(vector & nums) {29 set s(nums.begin(),nums.end());30 vector sorted(s.begin(),s.end());31 unordered_map um;32 int index = 1;33 for(auto i:s){34 um[i] = index;35 index++;36 }37 int m = nums.size();38 vector rank(m);39 for(int i = 0;i != nums.size();++i)40 rank[i] = um[nums[i]];41 int result = 0;42 FenwickTree tree(s.size());43 for(int i = m-1;i >= 0;--i){44 double target = nums[i]/2.0;45 if(target <= sorted[0]) {46 tree.update(rank[i]);47 continue;48 }49 int start = 0;50 int end = sorted.size()-1;51 while(start < end){52 int pivot = start+(end-start+1)/2;53 if(sorted[pivot] >= target)54 end = pivot-1;55 else56 start = pivot;57 }58 result += tree.getSum(um[sorted[start]]);59 tree.update(rank[i]);60 }61 return result;62 }63 };