四虎黄片,天天干天天日天天干,丁香六月婷婷五月,精品二区三区影院AV,北条麻纪一区二区三区在线视频 ,国产三级久久久精品麻豆三级,偷拍网首页,一起操在线

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做?翻轉(zhuǎn)對(duì)，我們先來(lái)看題面：

https://leetcode-cn.com/problems/reverse-pairs/

Given?an?integer?array?nums,?return?the?number?of?reverse?pairs?in?the?array. A?reverse?pair?is?a?pair?(i,?j)?where?0?<=?i??2?*?nums[j].

給定一個(gè)數(shù)組 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我們就將 (i, j) 稱作一個(gè)重要翻轉(zhuǎn)對(duì)。

你需要返回給定數(shù)組中的重要翻轉(zhuǎn)對(duì)的數(shù)量。

示例? ? ? ? ? ? ? ? ? ? ? ? ?

示例 1:
輸入: [1,3,2,3,1]
輸出: 2

示例 2:
輸入: [2,4,3,5,1]
輸出: 3

注意:
給定數(shù)組的長(zhǎng)度不會(huì)超過(guò)50000。
輸入數(shù)組中的所有數(shù)字都在32位整數(shù)的表示范圍內(nèi)。

解題

https://www.jianshu.com/p/6cc32f9e57c7

這道題可以采用歸并排序 + 二分查找來(lái)解決。我們可以先考慮一個(gè)最簡(jiǎn)單的情況，如 [-10, -6]，我們可以先將 [-10, -10] 分割為 L 和 R 兩個(gè)子數(shù)組，其中 L = [-10], R = [-6]。顯然，L 和 R 中都只有一個(gè)元素，本身就是有序數(shù)組，同時(shí)翻轉(zhuǎn)對(duì)數(shù)為0。將 L 和 R 合并排序，由于 L[0] > 2 * R[0], 得到排序后的數(shù)組為 [-10, -6], 且翻轉(zhuǎn)對(duì)數(shù)為 1。
上述過(guò)程大體上描繪了代碼主體的框架，要求出一個(gè)數(shù)組的翻轉(zhuǎn)對(duì)數(shù)，我們需要將其劃分為 L 和 R，并求出 L 和 R 中的翻轉(zhuǎn)對(duì)數(shù) v1 和 v2，然后對(duì)排好序的 L 和 R 進(jìn)行合并排序，得到翻轉(zhuǎn)對(duì)數(shù) v3，則數(shù)組本身的翻轉(zhuǎn)對(duì)數(shù)就是 v1 + v2 + v3。

class?Solution?{
public:
????using?ull = unsigned?long?long;
????static?const?int?MAX = 50000;
????long?long?L[MAX / 2?+ 2] = {0}, R[MAX / 2?+ 2] = {0};
????ull Merge(vector<int>& nums, int?left, int?mid, int?right){
????????int?L_end = mid - left;
????????int?R_end = right - mid;
????????for(int?i = 0;i < L_end;++i)
????????????L[i] = nums[left + i];
????????for(int?i = 0;i < R_end;++i)
????????????R[i] = nums[mid + i];
????????L[L_end] = static_cast<long?long>(numeric_limits<int>::max()) + 2;
????????R[R_end] = static_cast<long?long>(numeric_limits<int>::max()) + 2;
????????ull cnt = 0;
????????int?i = 0, j = 0;
????????for(int?k = left;k < right;++k){
????????????if(L[i] < R[j]){
????????????????nums[k] = L[i++];
????????????}else{
????????????????if(R[j] < 0)
????????????????????cnt += L_end - (upper_bound(L, L + L_end, R[j] * 2) - L);
????????????????else
????????????????????cnt += L_end - (upper_bound(L + i, L + L_end, R[j] * 2) - L);
????????????????nums[k] = R[j++];
????????????}
????????}
????????return?cnt;
????}
????int?MergeSort(vector<int>& nums, int?left, int?right){
????????ull v1 = 0, v2 = 0, v3 = 0;
????????if(left + 1?< right){
????????????int?mid = (left + right) >> 1;
????????????v1 = MergeSort(nums, left, mid);
????????????v2 = MergeSort(nums, mid, right);
????????????v3 = Merge(nums, left, mid, right);
????????}
????????return?v1 + v2 + v3;
????}
????int?reversePairs(vector<int>& nums)?{
????????return?MergeSort(nums, 0, nums.size());
????}
};