【Day 39 】2023-03-24 - 493. 翻转对

[azl397985856]

493. 翻转对

入选理由

暂无

题目地址

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

前置知识

• 二分法

  题目描述

  
  给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

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

输入: [2,4,3,5,1] 输出: 3 注意:

给定数组的长度不会超过50000。 输入数组中的所有数字都在32位整数的表示范围内。

[Zoeyzyzyzy]

class Solution {
    int[] nums;
    int[] temp;
    int count = 0;
    int n;

    public int reversePairs(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.temp = new int[n];
        mergeSort(0, n - 1);
        return count;
    }

    private void mergeSort(int left, int right) {
        if (left == right)
            return;
        int mid = (left + right) >>> 1;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        int i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if ((long)nums[i] > (long)2 * nums[j]) {
                count += mid - i + 1;
                j++;
            } else {
                i++;
            }
        }
        i = left;
        j = mid + 1;
        for (int p = left; p <= right; p++) {
            temp[p] = nums[p];
        }
        for (int p = left; p <= right; p++) {
            if (i == mid + 1) {
                nums[p] = temp[j++];
            } else if (j == right + 1 || temp[i] <= temp[j]) {
                nums[p] = temp[i++];
            } else {
                nums[p] = temp[j++];
            }
        }
    }
}

[JiangyanLiNEU]

• MergeSort
• T = O(NlogN)
• S = O(N)

  class Solution:
  def reversePairs(self, nums: List[int]) -> int:
      self.cnt = 0
      def mergeSort(array):
          if len(array)<=1:
              return array
          start, end, res = 0, len(array), []
          middle = (start+end)//2
          left, right = mergeSort(array[start:middle]), mergeSort(array[middle:end])
          i = j = 0
          while i<len(left) and j<len(right):
              if left[i] > 2*right[j]:
                  self.cnt += len(left)-i
                  j += 1
              else:
                  i += 1
          while left and right:
              if left[0] < right[0]:
                  res.append(left.pop(0))
              else:
                  res.append(right.pop(0))
          while left:
              res.append(left.pop(0))
          while right:
              res.append(right.pop(0))
          return res
      mergeSort(nums)
      return self.cnt

[huizsh]

‘‘‘ from sortedcontainers import SortedList class Solution: def reversePairs(self, A): d = SortedList() ans = 0

    for a in A:
        i = d.bisect_right(a * 2)
        ans += len(d) - i
        d.add(a)
    return ans

‘‘‘

[JasonQiu]

• Merge sort

  class Solution(object):
  def reversePairs(self, nums):
      def mergeSort(nums, left, right):
          if left >= right:
              return 0
          mid = left + (right - left) // 2
          result = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right)
          j = mid + 1
          for i in range(left, mid + 1):
              while j <= right and nums[i] > 2 * nums[j]:
                  j += 1
              result += j - (mid + 1)
          nums[left:(right + 1)] = sorted(nums[left:(right + 1)])
          return result
  
      return mergeSort(nums, 0, len(nums) - 1)

  Time: O(nlogn) Space: O(n)

[jackgaoyuan]

func reversePairs(nums []int) int {
    var res int
    mergeSort(nums, &res)
    return res
}
func mergeSort(nums []int, res *int) []int {
    if len(nums) <= 1 {
        return nums
    }
    var mergedArray []int
    array1 := nums[:(len(nums) - 1) / 2 + 1]
    array2 := nums[(len(nums) - 1) / 2 + 1:]
    sortArray1 := mergeSort(array1, res)
    sortArray2 := mergeSort(array2, res)
    for i := 0; i < len(sortArray1); i++ {
        m, n := 0, len(sortArray2) - 1
        for m < n {
            mid := m + (n - m) / 2
            if sortArray1[i] <= 2 * sortArray2[mid] {
                n = mid
            } else {
                m = mid + 1
            }
        }
        if sortArray1[i] > 2 * sortArray2[m] {
            m += 1
        }
        *res += m
    }
    for i, j := 0, 0; i < len(sortArray1) || j < len(sortArray2); {
        if i >= len(sortArray1) {
            mergedArray = append(mergedArray, sortArray2[j])
            j++
        } else if j >= len(sortArray2) {
            mergedArray = append(mergedArray, sortArray1[i])
            i++
        } else if sortArray1[i] <= sortArray2[j] {
            mergedArray = append(mergedArray, sortArray1[i])
            i++
        } else {
            mergedArray = append(mergedArray, sortArray2[j])
            j++
        }
    }
    return mergedArray
}

[Hughlin07]

class Solution {

public int reversePairs(int[] nums) {
    return mergeSort(nums, 0, nums.length-1);
}

public int mergeSort(int[] nums, int left, int right){
    if(left >= right) return 0;
    int mid = left + (right - left)/2;
    int result = mergeSort(nums, left, mid);
    result += mergeSort(nums, mid + 1, right);
    result += merge(nums, left, mid, right);
    return result;
}

public int merge(int[] nums, int left, int mid, int right){
    int cnt = 0;
    int j = mid + 1;
    for(int i = left; i <= mid; i++){
        while(j <= right && nums[i] > 2* (long)nums[j]){
            j++;
        }
        cnt += (j - (mid + 1));
    }

    ArrayList<Integer> tempNum = new ArrayList<>();
    int leftPin = left, rightPin = mid + 1;
    while(leftPin <= mid && rightPin <= right){
        if(nums[leftPin] <= nums[rightPin]){
            tempNum.add(nums[leftPin++]);
        }
        else{
            tempNum.add(nums[rightPin++]);
        }
    }

    while(leftPin <= mid){
        tempNum.add(nums[leftPin++]);
    }

    while(rightPin <= right){
        tempNum.add(nums[rightPin++]);
    }

    for(int i=left; i <= right; i++){
        nums[i] = tempNum.get(i-left);
    }

    return cnt; 
}

}

Time: O(nlogn)

Space: O(n)

[kofzhang]

思路（偷个懒吧）

维护一个有序list

复杂度

时间复杂度：O(n^2) 空间复杂度：O(n)

代码

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        res = 0
        target = []
        for i in nums[::-1]:
            insert = bisect_left(target,i/2)
            res += insert
            insort(target,i)
        return res

[FlipN9]

/**
    Approach 1: MergeSort       TC: O(NlogN)    SC: O(N)
*/
class Solution {
    public int reversePairs(int[] nums) {
        if (nums.length == 1) return 0;
        int N = nums.length;
        int[] helper = new int[N];
        return mergeSort(nums, helper, 0, N - 1);
    }

    private int mergeSort(int[] nums, int[] helper, int left, int right) {
        if (left >= right) return 0;
        int count = 0;
        int mid = left + (right - left) / 2;
        count += mergeSort(nums, helper, left, mid);
        count += mergeSort(nums, helper, mid + 1, right);
        count += merge(nums, helper, left, mid, right);
        return count;
    }

    private int merge(int[] nums, int[] helper, int left, int mid, int right) {
        for (int i = left; i <= right; i++) 
            helper[i] = nums[i];
        int count = 0;
        int i = left, j = mid + 1;
        // count the reverse pairs, 不能一边 count 一边 merge, 因为负数  

        // while (i <= mid && j <= right) {
        //     if ((long)array[i] > (long)array[j] * 2) {
        //         // count += mid + 1 - i;
        //         j++;
        //     } else {
        //         i++;
        //     }
        // }
        while (i <= mid) {
            while (j <= right && (long) nums[i] > (long) nums[j] * 2) {
                j++;
            }
            count += j - (mid + 1);
            i++;
        }
        // sort

        i = left;
        j = mid + 1;
        while (i <= mid) {
            if (j > right || helper[i] <= helper[j]) {
                nums[left++] = helper[i++];
                // count += j - (mid + 1);
            } else {
                nums[left++] = helper[j++];
                // count += mid + 1 - i;
            }
        }
        return count;
    }
}

[bookyue]

TC: O(nlgn)
SC: O(n)

binary indexed tree - loose discrete

    public int reversePairs(int[] nums) {
        int n = nums.length;
        var map = discrete(nums);
        int[] tree = new int[2 * n + 1];

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int index = map.get(nums[i] * 2L);
            ans += i - preSum(tree, index);
            index = map.get((long) nums[i]);
            add(tree, index);
        }

        return ans;
    }

    private void add(int[] tree, int index) {
        for (int i = index + 1; i < tree.length; i += i & -i)
            tree[i]++;
    }

    private int preSum(int[] tree, int index) {
        int sum = 0;
        for (int i = index + 1; i > 0; i -= i & -i)
            sum += tree[i];

        return sum;
    }

    private Map<Long, Integer> discrete(int[] nums) {
        Set<Long> set = new TreeSet<>();
        for (int num : nums) {
            set.add((long) num);
            set.add(num * 2L);
        }

        Map<Long, Integer> map = new HashMap<>();
        int idx = 0;
        for (Long x : set) 
            map.put(x, idx++);

        return map;
    }

TC: O(nlgn)
SC: O(n)

binary indexed tree - tight discrete

    public int reversePairs(int[] nums) {
        int n = nums.length;
        int[] sorted = Arrays.copyOf(nums, n);
        Arrays.sort(sorted);
        int[] tree = new int[n + 1];

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int index = getLastSmallerEqualPos(sorted, 2L * nums[i]);
            ans += i - preSum(tree, index);
            index = getLastSmallerEqualPos(sorted, nums[i]);
            add(tree, index);
        }

        return ans;
    }

    private void add(int[] tree, int index) {
        for (int i = index + 1; i < tree.length; i += i & -i)
            tree[i]++;
    }

    private int preSum(int[] tree, int index) {
        int sum = 0;
        for (int i = index + 1; i > 0; i -= i & -i)
            sum += tree[i];

        return sum;
    }

    /**
     * arr = {1, 3, 7, 7, 7, 8}
     * getLastSmallerEqualPos(arr, 7) = 4
     */
    private int getLastSmallerEqualPos(int[] sorted, long searched) {
        int left = 0;
        int right = sorted.length;
        searched++;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (searched <= sorted[mid])
                right = mid;
            else
                left = mid + 1;
        }

        return left - 1;
    }

[Abby-xu]

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def h(nums):
            if len(nums) <= 1: return nums, 0
            mid = len(nums) // 2
            lArr, lRes, rArr, rRes = *h(nums[:mid]), *h(nums[mid:])
            res, rIndex = lRes + rRes, 0
            for n in lArr:
                while rIndex < len(rArr) and rArr[rIndex] * 2 < n: rIndex += 1
                res += rIndex
            return sorted(nums), res 
        return h(nums)[1]

[GuitarYs]

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def h(nums):
            if len(nums) <= 1: return nums, 0
            mid = len(nums) // 2
            lArr, lRes, rArr, rRes = *h(nums[:mid]), *h(nums[mid:])
            res, rIndex = lRes + rRes, 0
            for n in lArr:
                while rIndex < len(rArr) and rArr[rIndex] * 2 < n: rIndex += 1
                res += rIndex
            return sorted(nums), res 
        return h(nums)[1]

[jmaStella]

思路

不会，看了答案 mergeSort 如果左边>右边2， 那么左边剩下后面的（before mid）全都会大于右边2 edge case：如果是很大的int，乘以二会超过边界，所以需要用 2*（long）NUMBER

代码

class Solution {
    int count;
    public int reversePairs(int[] nums) {
        count =0;
        mergeSort(nums, 0, nums.length-1);

        return count;
    }
    public void mergeSort(int[] nums, int start, int end){
        if(start >= end){
            return;
        }
        int mid = start+ (end - start)/2;

        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, end);
    }

    public void merge(int[] nums, int start, int mid, int end){
        int[] temp = new int[end -start +1];
        int left = start;
        int right = mid+1;
        int index = 0;
        while(left<=mid && right <=end){
            if(nums[left] < nums[right]){
                temp[index] = nums[left];
                left++;
            }else{
                temp[index] = nums[right];
                right++;
            }
            index++;
        }

        while(left <=mid){
            temp[index] = nums[left];
            left++;
            index++;
        }
        while(right <= end){
            temp[index] = nums[right];
            right++;
            index++;
        }
        int tleft = start;
        int tright = mid+1;
        while(tleft<=mid && tright <=end){
            //double cmp = double(nums[tleft]) - double(nums[tright]) - double(nums[tright]);
            //if(cmp >0){
            if(nums[tleft] > 2*(long)nums[tright]){
                count+= (mid - tleft)+1;
                tright++;
            }else{
                tleft++;
            }
        }

        for(int i = start; i<=end; i++){
            nums[i] = temp[i-start];
        }
    }
}

复杂度

时间 O(nlogn) 空间O(N)

[wangqianqian202301]

思路

分治法， 先分组， 再排序

代码

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        return self.countPairs(nums, 0, len(nums) - 1)

    def countPairs(self, nums: List[int], start: int, end: int) -> int:
        if start >= end:
            return 0
        mid = (start + end) // 2
        count = self.countPairs(nums, start, mid) + self.countPairs(nums, mid + 1, end)
        i, j = start, mid + 1
        while i <= mid and j <= end:
            if nums[i] > nums[j] * 2:
                count = count + end - j + 1
                i = i + 1
            else:
                j = j + 1

        nums[start : end + 1] = sorted(nums[start : end + 1], reverse=1)
        return count

复杂度

O(nlogn)

[aoxiangw]

def reversePairs(self, nums: List[int]) -> int:
    res = 0
    aux = []
    for y in nums:
        i = bisect.bisect_right(aux, y * 2)
        res += len(aux) - i
        bisect.insort(aux, y)
    return res

Time, space: O(nlogn), O(n)

[chanceyliu]

代码

const reversePairsRecursive = (nums, left, right) => {
  if (left === right) {
    return 0;
  } else {
    const mid = Math.floor((left + right) / 2);
    const n1 = reversePairsRecursive(nums, left, mid);
    const n2 = reversePairsRecursive(nums, mid + 1, right);
    let ret = n1 + n2;

    let i = left;
    let j = mid + 1;
    while (i <= mid) {
      while (j <= right && nums[i] > 2 * nums[j]) {
        j++;
      }
      ret += j - mid - 1;
      i++;
    }

    const sorted = new Array(right - left + 1);
    let p1 = left,
      p2 = mid + 1;
    let p = 0;
    while (p1 <= mid || p2 <= right) {
      if (p1 > mid) {
        sorted[p++] = nums[p2++];
      } else if (p2 > right) {
        sorted[p++] = nums[p1++];
      } else {
        if (nums[p1] < nums[p2]) {
          sorted[p++] = nums[p1++];
        } else {
          sorted[p++] = nums[p2++];
        }
      }
    }
    for (let k = 0; k < sorted.length; k++) {
      nums[left + k] = sorted[k];
    }
    return ret;
  }
};

function reversePairs(nums: number[]): number {
  if (nums.length === 0) {
    return 0;
  }
  return reversePairsRecursive(nums, 0, nums.length - 1);
}

复杂度分析

• 时间复杂度：O(N log N)
• 空间复杂度：O(N)

[FireHaoSky]

思路：并归排序

代码：python

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def find_reversed_pairs(nums, left,right):
            res,mid = 0, (left+(right-left)//2)
            j=mid+1
            for i in range(left,mid+1):
                while j <= right and nums[i] > 2*nums[j]:
                    res += mid-i+1
                    j+=1
            return res

        def merge_sort(nums, nums_sorted,l,r):
            if l >= r:return 0
            mid = l + (r-l)//2
            res = merge_sort(nums,nums_sorted,l,mid) +merge_sort(nums,nums_sorted, mid+1, r) +find_reversed_pairs(nums,l,r)

            i,j,k = l,mid+1,l
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    nums_sorted[k] = nums[i]
                    i += 1
                else:
                    nums_sorted[k] = nums[j]
                    j += 1
                k += 1
            while i <= mid:
                nums_sorted[k] = nums[i]
                i+=1
                k+=1
            while j <= r:
                nums_sorted[k] = nums[j]
                j+=1
                k+=1
            for k in range(l,r+1): nums[k] = nums_sorted[k]
            return res

        if not nums: return 0
        nums_sorted = [0]*len(nums)
        return merge_sort(nums,nums_sorted,0,len(nums)-1)

复杂度分析

"""
时间复杂度：O(nlogn)
空间复杂度：O(n)
"""

[chocolate-emperor]

归并排序求变种的逆序对。
需要注意的是，排序条件仍然是nums[i]>nums[j]，然后变种逆序对需要单独遍历循环求解，判断条件是nums[i]*0.5>nums[j]（防止大数溢出）
class Solution {
public:
    int res = 0;
    typedef long long LL;
    void mergeSort(vector<int>&nums,int l, int r){
        if(l>=r)    return;

        int mid = l+(r-l)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        //合并两段 l ... r

        vector<int>tmp;
        int i = l, j = mid+1;
        while(i<=mid && j <=r ){
            if(nums[i]>nums[j]){
                tmp.emplace_back(nums[j++]);
            }
            else    tmp.emplace_back(nums[i++]);
        }

        while(i<=mid)  tmp.emplace_back(nums[i++]);
        while(j<=r)    tmp.emplace_back(nums[j++]);

        i = l,j = mid+1;
        while(i<=mid && j<=r){
            if(nums[i]*0.5>nums[j]){
                res+= mid - i + 1;
                j+=1;
            }
            else    i+=1;
        }

        for(int i = 0; i<tmp.size() ; i++){
            nums[l+i] = tmp[i];
        }
        //swap_ranges(tmp.begin(),tmp.end(),nums.begin()+l);
        return;
    }
    int reversePairs(vector<int>& nums) {
        mergeSort(nums,0,nums.size()-1);
        return res;
    }
};

[linlizzz]

思路

分治法排序，合并的同时，若出现前一有序组i的值大于后一有序组j的值的两倍，则计数前一有序组i开始到最后一个元素的数量（其均大于后一有序组j的值的两倍）

代码

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.cnt = 0
        def merge(nums, l, r, mid):
            num1 = nums[l:mid+1]
            num2 = nums[mid+1:r+1]
            i, j = 0, 0
            temp = []

            while i < len(num1) and j < len(num2):
                if num1[i] <= num2[j]:
                    temp.append(num1[i])
                    i += 1
                else:
                    temp.append(num2[j])
                    j += 1

            while i < len(num1):
                temp.append(num1[i])
                i += 1
            while j < len(num2):
                temp.append(num2[j])
                j += 1
            nums[l:r+1] = temp

            i, j = 0, 0
            while i < len(num1) and j <len(num2):
                if num1[i] <= num2[j]*2:
                    i += 1
                else:
                    self.cnt += len(num1)-i
                    j += 1

        def mergesort(nums, l, r):
            if l >= r:
                return
            else:
                mid = (l+r)//2
                mergesort(nums, l, mid)
                mergesort(nums, mid+1, r)
            merge(nums, l, r, mid)

        mergesort(nums, 0, len(nums)-1)

        return self.cnt

复杂度分析

T(n) = O(nlogn)

S(n) = O(n)

[harperz24]

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        # define a helper function to count the number of reverse pairs recursively
        def mergeSort(start: int, end: int) -> int:
            # base case: if the subarray has less than 2 elements, return 0
            if start >= end:
                return 0

            mid = start + (end - start) // 2
            count = mergeSort(start, mid) + mergeSort(mid + 1, end)

            # count the number of reverse pairs between the two halves of the subarray
            i, j = start, mid + 1
            while i <= mid and j <= end:
                if nums[i] > 2 * nums[j]:
                    count += mid - i + 1
                    j += 1
                else:
                    i += 1

            # sort the subarray by merging its two halves
            nums[start:end+1] = sorted(nums[start:end+1])

            return count

        # call the helper function on the entire array and return the result
        return mergeSort(0, len(nums) - 1)

[joemonkeylee]

思路

没有做出来

代码

       public int ReversePairs(int[] nums) {
        if (nums.Length == 0) {
            return 0;
        }
        return reversePairsRecursive(nums, 0, nums.Length - 1);
    }

    public int reversePairsRecursive(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = reversePairsRecursive(nums, left, mid);
            int n2 = reversePairsRecursive(nums, mid + 1, right);
            int ret = n1 + n2;

            // 首先统计下标对的数量
            int i = left;
            int j = mid + 1;
            while (i <= mid) {
                while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {
                    j++;
                }
                ret += j - mid - 1;
                i++;
            }

            // 随后合并两个排序数组
            int[] sorted = new int[right - left + 1];
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = nums[p2++];
                } else if (p2 > right) {
                    sorted[p++] = nums[p1++];
                } else {
                    if (nums[p1] < nums[p2]) {
                        sorted[p++] = nums[p1++];
                    } else {
                        sorted[p++] = nums[p2++];
                    }
                }
            }
            for (int k = 0; k < sorted.Length; k++) {
                nums[left + k] = sorted[k];
            }
            return ret;
        }
    }

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[NorthSeacoder]

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    if (nums.length === 0) return 0;
    //存储已经扫描过的数字,有序的数组(2*nums[j])
    const arr = [];
    let res = 0;
    for (let i = nums.length - 1; i >= 0; i--) {
        //查询 arr 中所有小于 nums[i]的值
        //即翻转对的数量
        res += binarySearchLeft(arr, nums[i]);
        const n2 = 2 * nums[i];
        const index = binarySearchLeft(arr, n2);
        //插入新的 2*nums[j]
        arr.splice(index, 0, n2);
    }
    return res;
};
//在 arr 中查询 num 插入的最左侧位置
//同时也是 arr 中小于 num 的数量
const binarySearchLeft = (arr, num) => {
    let start = 0;
    let end = arr.length;
    while (start <= end) {
        const mid = Math.floor((start + end) / 2);
        if (arr[mid] < num) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return start;
};

-TC:O(nlogn)

• SC:O(n)

[duke-github]

思路

归并排序

复杂度

时间复杂度O(n log n) 空间复杂度O(n)

代码

class Solution {
    public int reversePairs(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        return reversePairsRecursive(nums, 0, nums.length - 1);
    }

    public int reversePairsRecursive(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = reversePairsRecursive(nums, left, mid);
            int n2 = reversePairsRecursive(nums, mid + 1, right);
            int ret = n1 + n2;

            // 首先统计下标对的数量
            int i = left;
            int j = mid + 1;
            while (i <= mid) {
                while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {
                    j++;
                }
                ret += j - mid - 1;
                i++;
            }

            // 随后合并两个排序数组
            int[] sorted = new int[right - left + 1];
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = nums[p2++];
                } else if (p2 > right) {
                    sorted[p++] = nums[p1++];
                } else {
                    if (nums[p1] < nums[p2]) {
                        sorted[p++] = nums[p1++];
                    } else {
                        sorted[p++] = nums[p2++];
                    }
                }
            }
            for (int k = 0; k < sorted.length; k++) {
                nums[left + k] = sorted[k];
            }
            return ret;
        }
    }
}

[wangzh0114]

class Solution {
public:
    int reversePairsRecursive(vector<int>& nums, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = reversePairsRecursive(nums, left, mid);
            int n2 = reversePairsRecursive(nums, mid + 1, right);
            int ret = n1 + n2;
            int i = left;
            int j = mid + 1;
            while (i <= mid) {
                while (j <= right && (long long)nums[i] > 2 * (long long)nums[j]) j++;
                ret += (j - mid - 1);
                i++;
            }
            vector<int> sorted(right - left + 1);
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = nums[p2++];
                } else if (p2 > right) {
                    sorted[p++] = nums[p1++];
                } else {
                    if (nums[p1] < nums[p2]) {
                        sorted[p++] = nums[p1++];
                    } else {
                        sorted[p++] = nums[p2++];
                    }
                }
            }
            for (int i = 0; i < sorted.size(); i++) {
                nums[left + i] = sorted[i];
            }
            return ret;
        }
    }

    int reversePairs(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        return reversePairsRecursive(nums, 0, nums.size() - 1);
    }
};

[tzuikuo]

思路

归并的过程中记录逆序对数目

代码

class Solution {
public:
    int cnt=0;
    int reversePairs(vector<int>& nums) {
        int n=nums.size();
        mergesort(nums,0,n-1);
        return cnt;
    }
    void mergesort(vector<int>& nums,int left,int right){
      vector<int> temp;
      int n=nums.size();
      if(left==right){
        temp.push_back(nums[left]);
      }
      else if(left==right-1){
        if(nums[left]>(long long) 2*nums[right]) cnt++;
        if(nums[left]>nums[right]){
          temp.push_back(nums[right]);
          temp.push_back(nums[left]);
        }
        else{
          temp.push_back(nums[left]);
          temp.push_back(nums[right]);
        }
      }
      else{
        int med=(right+left)/2;
        mergesort(nums,left,med);
        mergesort(nums,med+1,right);
        int ii=left,jj=med+1;
        int j=med+1;
        for(int i=left;i<=med;i++){
            while(j<=right&&nums[i]>(long long)2*nums[j]){
                cnt+=(med-i+1);
                j++;
            }
        }          
        while(ii<=med||jj<=right){
          if(ii<=med&&jj>right){
            temp.push_back(nums[ii]);
            ii++;
          }
          else if(ii>med&&jj<=right){
            temp.push_back(nums[jj]);
            jj++;
          }
          else{
            if(nums[ii]>nums[jj]){
              temp.push_back(nums[jj]);
              jj++;
            }
            else{
              temp.push_back(nums[ii]);
              ii++;
            }
          }
        }
      }
      for(int i=left;i<=right;i++){
          nums[i]=temp[i-left];
      }
      return;
    }
};

复杂度分析

• 时间O(nlogn)
• 空间O(n)

[ZhuMengCheng]

看懂了题目,但没思路, 答案参考题解
/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    if (nums.length === 0) {
        return 0;
    }
    return reversePairsRecursive(nums, 0, nums.length - 1);
};

const reversePairsRecursive = (nums, left, right) => {
    if (left === right) {
        return 0;
    } else {
        const mid = Math.floor((left + right) / 2);
        const n1 = reversePairsRecursive(nums, left, mid);
        const n2 = reversePairsRecursive(nums, mid + 1, right);
        let ret = n1 + n2;

        let i = left;
        let j = mid + 1;
        while (i <= mid) {
            while (j <= right && nums[i] > 2 * nums[j]) {
                j++;
            }
            ret += j - mid - 1;
            i++;
        }

        const sorted = new Array(right - left + 1);
        let p1 = left, p2 = mid + 1;
        let p = 0;
        while (p1 <= mid || p2 <= right) {
            if (p1 > mid) {
                sorted[p++] = nums[p2++];
            } else if (p2 > right) {
                sorted[p++] = nums[p1++];
            } else {
                if (nums[p1] < nums[p2]) {
                    sorted[p++] = nums[p1++];
                } else {
                    sorted[p++] = nums[p2++];
                }
            }
        }
        for (let k = 0; k < sorted.length; k++) {
            nums[left + k] = sorted[k];
        }
        return ret;
    }

};

复杂度分析

时间复杂度：O(Nlog⁡N)

空间复杂度：O(N)

[kangliqi1]

class Solution { public int reversePairs(int[] nums) { if (nums.length == 0) { return 0; } return reversePairsRecursive(nums, 0, nums.length - 1); }

public int reversePairsRecursive(int[] nums, int left, int right) {
    if (left == right) {
        return 0;
    } else {
        int mid = (left + right) / 2;
        int n1 = reversePairsRecursive(nums, left, mid);
        int n2 = reversePairsRecursive(nums, mid + 1, right);
        int ret = n1 + n2;

        // 首先统计下标对的数量
        int i = left;
        int j = mid + 1;
        while (i <= mid) {
            while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {
                j++;
            }
            ret += j - mid - 1;
            i++;
        }

        // 随后合并两个排序数组
        int[] sorted = new int[right - left + 1];
        int p1 = left, p2 = mid + 1;
        int p = 0;
        while (p1 <= mid || p2 <= right) {
            if (p1 > mid) {
                sorted[p++] = nums[p2++];
            } else if (p2 > right) {
                sorted[p++] = nums[p1++];
            } else {
                if (nums[p1] < nums[p2]) {
                    sorted[p++] = nums[p1++];
                } else {
                    sorted[p++] = nums[p2++];
                }
            }
        }
        for (int k = 0; k < sorted.length; k++) {
            nums[left + k] = sorted[k];
        }
        return ret;
    }
}

}

[Lydia61]

493. 翻转对

思路

模拟归并排序，分而治之

代码

class Solution {
public:
    int find_reversed_pairs(vector<int>& nums,int& left,int& right){
        int res = 0,mid = left + (right-left)/2;
        int i = left,j = mid+1;
        for(;i <= mid;i++){
            while(j <= right && (long)nums[i] > 2*(long)nums[j]) {
                res += mid - i + 1;
                j++;
            }
        }
        return res;
    }

    int merge_sort(vector<int>& nums,int nums_sorted[],int left,int right){
        if(left >= right) return 0;
        int mid = left + (right-left) / 2;

        int res = merge_sort(nums,nums_sorted,left,mid) + 
                  merge_sort(nums,nums_sorted,mid+1,right) + 
                  find_reversed_pairs(nums,left,right);

        int i = left,j = mid+1,ind = left;

        while(i <= mid && j <= right){
            if(nums[i] <= nums[j]) nums_sorted[ind++] = nums[i++];
            else nums_sorted[ind++] = nums[j++];
        }
        while(i <= mid) nums_sorted[ind++] = nums[i++];
        while(j <= right) nums_sorted[ind++] = nums[j++];

        for(int ind = left;ind <= right;ind++) nums[ind] = nums_sorted[ind];

        return res;
    }

    int reversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        int nums_sorted[nums.size()];
        memset(nums_sorted,0,sizeof(nums_sorted));
        return merge_sort(nums,nums_sorted,0,nums.size()-1);
    }
};

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[X1AOX1A]

0493. 翻转对

题目

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

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

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

思路1：暴力法（超时）

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            for j in range(n):
                if i<j and nums[i] > 2*nums[j]:
                    ans += 1
        return ans

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

思路2：二分法

• 这道题我们也可以反向思考，即：*对于 nums 中的每一项 num，我们找前面出现过的大于 num 2 的数**

思路

• 一边遍历数组，一边构造有序数组（SortedList in Python）
  • 如果使用 array 的话，插入的时间复杂度将会是 O(n^2)
  • 因此需要使用有序数组
• 判断前面出现过的大于 num * 2 的数量

代码

from sortedcontainers import SortedList
class Solution:
    def reversePairs(self, A):
        s = SortedList()
        ans = 0

        for a in A:
            # 获取当前 s 中大于 a*2 的 index
            i = s.bisect_right(a * 2)
            # 计算当前 s 中大于 a*2 的个数
            ans += len(s) - i
            # 将 a 加入到有序列表，O(nlogn)
            s.add(a)
        return ans

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[RestlessBreeze]

code

class Solution {
public:
    int reversePairsRecursive(vector<int>& nums, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = reversePairsRecursive(nums, left, mid);
            int n2 = reversePairsRecursive(nums, mid + 1, right);
            int ret = n1 + n2;

            int i = left;
            int j = mid + 1;
            while (i <= mid) {
                while (j <= right && (long long)nums[i] > 2 * (long long)nums[j]) j++;
                ret += (j - mid - 1);
                i++;
            }

            vector<int> sorted(right - left + 1);
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = nums[p2++];
                } else if (p2 > right) {
                    sorted[p++] = nums[p1++];
                } else {
                    if (nums[p1] < nums[p2]) {
                        sorted[p++] = nums[p1++];
                    } else {
                        sorted[p++] = nums[p2++];
                    }
                }
            }
            for (int i = 0; i < sorted.size(); i++) {
                nums[left + i] = sorted[i];
            }
            return ret;
        }
    }

    int reversePairs(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        return reversePairsRecursive(nums, 0, nums.size() - 1);
    }
};

[Fuku-L]

代码

class Solution {
    public int reversePairs(int[] nums) {
        if(nums.length == 0) return 0;
        return reversePairsRecursive(nums, 0, nums.length - 1);
    }
    public int reversePairsRecursive(int[] nums, int l, int r){
        if(l == r){
            return 0;
        } else {
            int mid = (l + r) /2;
            int n1 = reversePairsRecursive(nums, l, mid);
            int n2 = reversePairsRecursive(nums, mid+1, r);
            int res = n1 + n2;
            // 统计下标对数量
            int i = l;
            int j = mid + 1;
            while(i <= mid){
                while(j <= r && (long) nums[i] > 2 *(long)nums[j]){
                    j ++;
                }
                res += j - mid - 1;
                i++;
            }

            // 合并两个排序数组
            int[] sort = new int[r - l + 1];
            int p1 = l, p2 = mid + 1;
            int p = 0;
            while(p1 <= mid || p2 <= r){
                if(p1 > mid){
                    sort[p++] = nums[p2++];
                } else if(p2 > r) {
                    sort[p++] = nums[p1++];
                } else{
                    if(nums[p1] < nums[p2]){
                        sort[p++] = nums[p1++];
                    } else{
                        sort[p++] = nums[p2++];
                    }
                }
            }
            for(int k = 0; k < sort.length; k++){
                nums[l + k] = sort[k];
            }
            return res;
        }
    }
}

[snmyj]

class Solution {
public:
    int reversePairsRecursive(vector<int>& nums, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = reversePairsRecursive(nums, left, mid);
            int n2 = reversePairsRecursive(nums, mid + 1, right);
            int ret = n1 + n2;
            int i = left;
            int j = mid + 1;
            while (i <= mid) {
                while (j <= right && (long long)nums[i] > 2 * (long long)nums[j]) j++;
                ret += (j - mid - 1);
                i++;
            }
            vector<int> sorted(right - left + 1);
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = nums[p2++];
                } else if (p2 > right) {
                    sorted[p++] = nums[p1++];
                } else {
                    if (nums[p1] < nums[p2]) {
                        sorted[p++] = nums[p1++];
                    } else {
                        sorted[p++] = nums[p2++];
                    }
                }
            }
            for (int i = 0; i < sorted.size(); i++) {
                nums[left + i] = sorted[i];
            }
            return ret;
        }
    }

    int reversePairs(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        return reversePairsRecursive(nums, 0, nums.size() - 1);
    }
};

[yingchehu]

from sortedcontainers import SortedList

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        s = SortedList()
        ans = 0

        for n in nums:
            x = s.bisect_right(n * 2)
            ans += (len(s) - x)
            # 用 sorted list 可以讓加入元素的複雜度從 bisect.insort 的 O(N) 降低為 O(logN)
            s.add(n)
        return ans

[lp1506947671]

class Solution:
    def reversePairs(self, nums) -> int:
        self.cnt = 0
        def merge(nums, start, mid, end, temp):
            i, j = start, mid + 1
            while i <= mid and j <= end:
                if nums[i] <=  nums[j]:
                    temp.append(nums[i])
                    i += 1
                else:
                    temp.append(nums[j])
                    j += 1
            # 防住
            # 这里代码开始
            ti, tj = start, mid + 1
            while ti <= mid and tj <= end:
                if nums[ti] <=  2 * nums[tj]:
                    ti += 1
                else:
                    self.cnt += mid - ti + 1
                    tj += 1
            # 这里代码结束
            while i <= mid:
                temp.append(nums[i])
                i += 1
            while j <= end:
                temp.append(nums[j])
                j += 1
            for i in range(len(temp)):
                nums[start + i] = temp[i]
            temp.clear()

        def mergeSort(nums, start, end, temp):
            if start >= end: return
            mid = (start + end) >> 1
            mergeSort(nums, start, mid, temp)
            mergeSort(nums, mid + 1, end, temp)
            merge(nums, start, mid,  end, temp)
        mergeSort(nums, 0, len(nums) - 1, [])
        return self.cnt

复杂度分析

令 n 为数组长度。

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[AstrKing]

class Solution { public int reversePairs(int[] nums) { if(nums.length == 0) return 0; return reversePairsRecursive(nums, 0, nums.length - 1); } public int reversePairsRecursive(int[] nums, int l, int r){ if(l == r){ return 0; } else { int mid = (l + r) /2; int n1 = reversePairsRecursive(nums, l, mid); int n2 = reversePairsRecursive(nums, mid+1, r); int res = n1 + n2; // 统计下标对数量 int i = l; int j = mid + 1; while(i <= mid){ while(j <= r && (long) nums[i] > 2 *(long)nums[j]){ j ++; } res += j - mid - 1; i++; }

        // 合并两个排序数组
        int[] sort = new int[r - l + 1];
        int p1 = l, p2 = mid + 1;
        int p = 0;
        while(p1 <= mid || p2 <= r){
            if(p1 > mid){
                sort[p++] = nums[p2++];
            } else if(p2 > r) {
                sort[p++] = nums[p1++];
            } else{
                if(nums[p1] < nums[p2]){
                    sort[p++] = nums[p1++];
                } else{
                    sort[p++] = nums[p2++];
                }
            }
        }
        for(int k = 0; k < sort.length; k++){
            nums[l + k] = sort[k];
        }
        return res;
    }
}

}

[DrinkMorekaik]

var reversePairs = function (nums) {
    let count = 0
    let mergeArr = (left, right) => {
        let i = 0, j = 0
        while (i < left.length && j < right.length) {
            if (left[i] > 2 * right[j]) {
                count += left.length - i
                j++
            } else {
                i++
            }
        }
        return [...left, ...right].sort((a, b) => a - b)
    }

    let divide = (arr) => {
        if (arr.length <= 1) {
            return arr
        }
        let mid = (arr.length / 2) | 0
        let left = arr.slice(0, mid)
        let right = arr.slice(mid)
        return mergeArr(divide(left), divide(right))
    }

    divide(nums)
    return count
}

[zpbc007]

var reversePairs = function(nums) {
    if (nums.length === 0) {
        return 0;
    }
    return reversePairsRecursive(nums, 0, nums.length - 1);
};

const reversePairsRecursive = (nums, left, right) => {
    if (left === right) {
        return 0;
    } else {
        const mid = Math.floor((left + right) / 2);
        const n1 = reversePairsRecursive(nums, left, mid);
        const n2 = reversePairsRecursive(nums, mid + 1, right);
        let ret = n1 + n2;

        let i = left;
        let j = mid + 1;
        while (i <= mid) {
            while (j <= right && nums[i] > 2 * nums[j]) {
                j++;
            }
            ret += j - mid - 1;
            i++;
        }

        const sorted = new Array(right - left + 1);
        let p1 = left, p2 = mid + 1;
        let p = 0;
        while (p1 <= mid || p2 <= right) {
            if (p1 > mid) {
                sorted[p++] = nums[p2++];
            } else if (p2 > right) {
                sorted[p++] = nums[p1++];
            } else {
                if (nums[p1] < nums[p2]) {
                    sorted[p++] = nums[p1++];
                } else {
                    sorted[p++] = nums[p2++];
                }
            }
        }
        for (let k = 0; k < sorted.length; k++) {
            nums[left + k] = sorted[k];
        }
        return ret;
    }
}

[Jetery]

···cpp typedef long long LL; class Solution { public:

LL add(vector<int> &nums, int l, int r, int mid) {
    int i = l, j = mid + 1;
    LL ret = 0;
    while (i <= mid && j <= r) {
        if (nums[i] > (LL)nums[j] * 2) {
            ret += mid - i + 1;
            j++;
        } else {
            i++;
        }
    }
    return ret;
}

LL merge(vector<int> &nums, vector<int> &temp, int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) >> 1;
    LL ret = merge(nums, temp, l, mid) + merge(nums, temp, mid + 1, r) + add(nums, l, r, mid);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) temp[k++] = nums[i++];
        else temp[k++] = nums[j++];
    }
    while(i <= mid) temp[k++] = nums[i++];
    while(j <= r) temp[k++] = nums[j++];
    for (i = l, k = 0; i <= r; i++, k++) nums[i] = temp[k];
    return ret;
}

int reversePairs(vector<int>& nums) {
    int n = nums.size();
    vector<int> temp(n);
    return merge(nums, temp, 0, n - 1);
}

}; ···