歸併排序

Count of Range Sum

Reverse Pairs

Count of Smaller Numbers After Self

Global and Local Inversions

技巧:

1. 分而治之，歸併排序O(nlogn)
2. 歸併的過程中記錄結果，並且排序

套路:

class Solution {public: int reversePairs(vector<int>& nums) { vector<long> ns; // 設置需要求解的數組 for (auto num: nums) ns.push_back(num); return MergeSortWhileCount(ns, 0, nums.size()); } int MergeSortWhileCount(vector<long>& nums, int lo, int hi) { // 如果只有一個數，沒有可比性 if (hi-lo<=1) return 0; int mid = lo + (hi - lo) / 2; // 分治 int res = MergeSortWhileCount(nums, lo, mid) + MergeSortWhileCount(nums, mid, hi); int l = 0, t = mid, j = mid; vector<long> cache(hi-lo); // 從lo開始比較 for (int i=lo; i < mid; i++) { // ** 為滿足的條件 while (j < hi && **) j++; res += j - mid; // 保存順序 while (t < hi && nums[i] > nums[t]) cache[l++] = nums[t++]; cache[l++] = nums[i]; } // 覆蓋lo開始的l個數，歸併排序 for (int i=0; i < l; i++) nums[lo+i] = cache[i]; return res; }};

Count of Range Sum

題意: 求連續序列在[lower, upper]區間的個數

思路: 先求sums[i] = nums[0,1,...,i-1], sums[0] = 0, 然後對sums進行merge sort

class Solution {public: int countRangeSum(vector<int>& nums, int lower, int upper) { int n = nums.size(); vector<long> sums(n+1, 0); for (int i = 0; i < n; i++) sums[i+1] = sums[i] + nums[i]; return MergeSortWhileCount(sums, 0, n+1, lower, upper); } int MergeSortWhileCount(vector<long>& nums, int start, int end, int lower, int upper) { if (end-start <= 1) return 0; int mid = start + (end - start) / 2; int count = MergeSortWhileCount(nums, start, mid, lower, upper) + MergeSortWhileCount(nums, mid, end, lower, upper); int l = 0, t = mid, k = mid, j = mid; vector<long> cache(end-start); for (int i=start; i<mid; i++) { while (k < end && nums[k]-nums[i] < lower) k++; while (j < end && nums[j]-nums[i] <= upper) j++; count += ((j - k) <= 0 ? 0 : (j - k)); while (t < end && nums[i] > nums[t]) cache[l++] = nums[t++]; cache[l++] = nums[i]; } for (int i=0; i<l; i++) nums[start+i] = cache[i]; return count; }};

Reverse Pairs

題意: 求數組中滿足i < j and nums[i] > 2*nums[j] 的個數

思路: merge sort O(nlogn)

class Solution {public: int reversePairs(vector<int>& nums) { vector<long> ns; for (auto num: nums) ns.push_back(num); return MergeSortWhileCount(ns, 0, nums.size()); } int MergeSortWhileCount(vector<long>& nums, int lo, int hi) { if (hi-lo<=1) return 0; int mid = lo + (hi - lo) / 2; int res = MergeSortWhileCount(nums, lo, mid) + MergeSortWhileCount(nums, mid, hi); int l = 0, t = mid, j = mid; vector<long> cache(hi-lo); for (int i=lo; i < mid; i++) { while (j < hi && nums[i] > 2 * nums[j]) j++; res += j - mid; while (t < hi && nums[i] > nums[t]) cache[l++] = nums[t++]; cache[l++] = nums[i]; } for (int i=0; i < l; i++) nums[lo+i] = cache[i]; return res; }};

Count of Smaller Numbers After Self

題意: 求數組中每個元素的右邊比其小的個數

nums = [5, 2, 6, 1]return [2, 1, 1, 0]

思路: merge sort, 注意歸併排序的過程中更新每個計數的位置

class Solution {public: vector<int> countSmaller(vector<int>& nums) { vector<int> position, cnt(nums.size(), 0); for (int i=0; i < nums.size(); i++) position.push_back(i); MergeSortWhileCount(cnt, nums, position, 0, nums.size()); return cnt; } void MergeSortWhileCount(vector<int>& cnt, vector<int>& nums, vector<int>& position, int start, int end) { if (end-start <= 1) return ; int mid = start + (end - start) / 2; MergeSortWhileCount(cnt, nums, position, start, mid); MergeSortWhileCount(cnt, nums, position, mid, end); int l = 0, t = mid, k = mid; vector<int> cache_nums(end-start), cache_position(end-start); for (int i=start; i < mid; i++) { while (k < end && nums[i] > nums[k]) k++; cnt[position[i]] += k - mid; while (t < end && nums[i] > nums[t]) { cache_nums[l] = nums[t]; cache_position[l++] = position[t++]; } cache_nums[l] = nums[i], cache_position[l++] = position[i]; } for (int i=0; i < l; i++) { nums[start+i] = cache_nums[i]; position[start+i] = cache_position[i]; } }};

Global and Local Inversions

題意: 數組A是0~n-1的一個全排列, global inversions表示0 <= i < j < N and A[i] > A[j]的個數，local inversions表示0 <= i < N and A[i] > A[i+1]的個數，如果global inversions的個數等於local inversions的個數則返回true，否則返回false

觀察: 0~n-1的全排列滿足global數目等於local數目，必然滿足[0, 1, ..., n-1], 相鄰兩個數保持順序或翻轉順序, 意味著| A[i] - i | <= 1，時間複雜度O(n)

class Solution {public: bool isIdealPermutation(vector<int>& A) { for (int i=0; i<A.size(); i++) if (abs(A[i]-i) > 1) return false; return true; }};

如果題目沒有說明數組A的特徵，那麼需要使用mergesort咯

class Solution {public: bool isIdealPermutation(vector<int>& A) { int local_inversions = 0, global_inversions = 0; for (int i=0; i+1 < A.size(); i++) if (A[i] > A[i+1]) local_inversions++; global_inversions = MergeSortWhileCount(A, 0, A.size()); return local_inversions == global_inversions; } int MergeSortWhileCount(vector<int>& nums, int start, int end) { if (end-start <= 1) return 0; int mid = start+(end-start)/2; int count = MergeSortWhileCount(nums, start, mid) + MergeSortWhileCount(nums, mid, end); int l = 0, t = mid, k = mid; vector<int> cache(end-start); for (int i=start; i<mid; i++) { while (k < end && nums[i] > nums[k]) k++; count += (k - mid); while (t < end && nums[i] > nums[t]) cache[l++] = nums[t++]; cache[l++] = nums[i]; } for (int i=0; i<l; i++) nums[start+i] = cache[i]; return count; }};

推薦閱讀：