【Day 39 】2021-10-18 - 762.Number Stream to Intervals

[azl397985856]

762.Number Stream to Intervals

入选理由

暂无

题目地址

https://binarysearch.com/problems/Triple-Inversion

前置知识

• 二分法

  题目描述

  
  Given a list of integers nums, return the number of pairs i < j such that nums[i] > nums[j] * 3.

Constraints

n ≤ 100,000 where n is the length of nums Example 1 Input nums = [7, 1, 2] Output 2 Explanation We have the pairs (7, 1) and (7, 2)

[yanglr]

思路

方法: 二分搜索

二分搜索一般要求在一个有序的数据结构中进行搜索, 使用一个基于key排序的哈希表(C++中可以用Map, Java中可以用TreeMap), 映射为: value -> 出现的次数count。

我们可以进行逆向思考, 每次把一个新的数nums[i]放入哈希表之前把原数组nums中位置在它之前的元素都放进自动排序的哈希表，那么问题就转化为在这个key从小到大的哈希表中寻找 > 3*nums[i] 的数的个数了, C++中的map::upper_bound()可以轻松完成需要做的二分搜索。

最后把搜索到的成对的数量累加即可。

代码

实现语言: C++

int solve(vector<int>& nums) {
    map<int, int> dict;
    int res = 0;
    for (auto& num : nums)
    {
        auto it = dict.upper_bound(3*num); // 找到第1个满足要求的数key1, 那哈希表中排在key1后面的数(比key1更大)也全满足 > 3*num
        if (it != dict.end())
        {
            for (auto it1 = it; it1 != dict.end(); it1++)
                res += it1->second;
        }        

        if (dict.count(num) > 0)
            dict[num]++; 
        else dict[num] = 1;      
    }
    return res;
}

复杂度分析

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

方法2: 归并排序

速度确实快一些

实现语言: C++

void mergesort(vector<int> &nums, vector<int> &temp, int left, int right, int &result)
{
    if (left >= right) return;                     // base case: 只剩一个元素就是有序的了
    int mid = left + (right - left) / 2;           
    mergesort(nums, temp, left, mid, result);      //对左区间排序
    mergesort(nums, temp, mid + 1, right, result); //对右区间排序
    int i = left;
    int j = mid + 1;
    while (i <= mid && j <= right) // 左右区间都是有序的了，进行统计操作
    {
        if ((long long)nums[i] > 3 * (long long)nums[j]) // *3 会超 int 范围
        {
            result += (mid - i + 1); //反转对个数
            j++;
        }
        else i++;
    }

    i = left;
    j = mid + 1;
    int p = 0;
    while (i <= mid && j <= right) // 进行归并操作
    {
        if (nums[i] > nums[j])
            temp[p++] = nums[j++];
        else
            temp[p++] = nums[i++];
    }
    while (i <= mid) //将左边剩余元素填充进temp中
        temp[p++] = nums[i++];
    while (j <= right) //将右序列剩余元素填充进temp中
        temp[p++] = nums[j++];
    p = 0;
    while (left <= right) //将temp中的元素全部拷贝到原数组[left,right]中
        nums[left++] = temp[p++];
}

int solve(vector<int>& nums) {
    int size = nums.size();
    int left = 0;
    int right = size - 1;
    int result = 0;
    vector<int> temp(size);
    mergesort(nums, temp, left, right, result);
    return result;
}

复杂度分析

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

[JiangyanLiNEU]

Idea (Accidentally did Leetcode 726, so I update my answer of Triple Inversion)

• maintain a sortedlist called hold to store all the elements that we visited
• every time we visit a new number, we need to find the index in the hold, after which all the elements in hold is greater than number*3
• update result, and push new number into the sortedlist
• Runtime = O(nlogn) -- it took logn to get the index, but maintain the sortedlist took nlogn
• Space = O(n)

  Python Code

  class Solution:
  def solve(self, nums):
      hold = sortedcontainers.SortedList()
      result = 0
      for index, num in enumerate(nums):
          result += len(hold) - hold.bisect_right(num * 3)
          hold.add(num)
      return result

[q815101630]

翻转对

https://leetcode-cn.com/problems/reverse-pairs/ 两种方法

Merge Sort

在归并排序中，在最后return时，我们会做merge，因为merge时两个list（A，B)都自身有序，那么当A[i] > 3B[j] 时，我们知道i和i后面的数字都可以和j组成一对。cnt+=mid-i+1

Bisect

使用bisect_right可以得到在有序列表中小于等于某个值的个数， 那么我们可以做 bisect_right(nums[j]*3) 就可以找到<=nums[j]*3的个数，那么用列表总长减去这个值就是大于它的个数。为了确保i<j，遍历时只需要每次把当前元素加到有序列表中，必然 i<j。那么问题就转化成了：每次出现一个新元素，想知道一个有序列表内大于3倍新元素的元素个数。我们重复当前子问题n次即可。

python

class Solution:
    def solve(self, nums):
        self.counter = 0

        def merge(nums, left, mid, right, temp):
            i,j = left, mid+1
            while i <=mid and j<=right:
                if nums[i] < nums[j]:
                    temp.append(nums[i])
                    i+=1
                else:
                    temp.append(nums[j])
                    j+=1

            while i <=mid:
                temp.append(nums[i])
                i+=1

            while j <=right:
                temp.append(nums[j])
                j+=1

            i,j = left, mid+1

            while i <= mid and j <= right:
                if nums[i] > nums[j]*3:
                    self.counter += mid-i+1
                    j+=1
                else:
                    i+=1

            k = left
            for i in temp:
                nums[k] = i
                k+=1
            temp.clear()

        def mergesort(nums, left, right):
            if left >= right:
                return None
            temp = []
            mid = left+(right-left)//2
            mergesort(nums, left, mid)
            mergesort(nums, mid+1, right)
            merge(nums, left, mid, right, temp)

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

        return self.counter

# bisect
class Solution:
    # brutal force: TLE
    # def solve(self, nums):
    #     ans = 0
    #     for i in range(len(nums)):
    #         for j in range(i+1, len(nums)):
    #             if nums[i]>nums[j]*3:
    #                 ans+=1

    #     return ans
    def solve(self, nums):
        '''
        To bisect, we need an ordered list
        We use SortedList as a orderedList, where bisect_right allows knowing how many <= 3*i
        len(lis) - that amount = what is > 3*i
        then append curr to lis
        '''
        lis = SortedList()
        counter = 0
        for i in nums:
            p = lis.bisect_right(3*i)
            counter+=len(lis)-p

            lis.add(i)

        return counter

时空复杂度

Merge Sort：

时间：$$T(n) = 2T(\frac{n}{2})+f(n)$$ => O(n*logn)

空间：O(n)

Bisect：

时间： O(n*logn)

空间：O(n)

[Jackielj]

reverse pairs

class Solution {
    public int reversePairs(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = res + i - rightInsert(list, nums[i] * 2L);
            list.add(rightInsert(list, nums[i]), nums[i]);
        }
        return res;
    }

    public int rightInsert(List<Integer> list, long target) {
        int l = 0, r = list.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (list.get(mid) <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

时空复杂度： 时间：O(n*logn) 空间：O(n)

[Weisday]

class Solution {
  public int countPrimeSetBits(int L, int R) {
    int ans = 0;
    for (int n = L; n <= R; ++n)
      if (isPrime(bits(n))) ++ans;
    return ans;
  }

  private boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;      
    for (int i = 2; i <= (int)Math.sqrt(n); ++i)
      if (n % i == 0) return false;
    return true;
  }

  private int bits(int n) {
    int s = 0;
    while (n != 0) {
      s += n & 1;
      n >>= 1;
    }        
    return s;
  }
}

//空间复杂： O(n)
//时间复杂：O(nlogn)

[nonevsnull]

思路

• 拿到题的直觉解法
  • 二分的题，目标是将题目匹配到模板；
  • 没匹配，就没想清楚，做出来也没意义；下次还是错；
  • 二分需要sort，但是题目没有sort，因此考虑对每个位置的元素，sort后找到合适的插入位置，然后求解；
  • 这里的二分模版应该是用的是：寻找最右插入位置或者寻找最左符合条件(大于x的值)，如果要用符合条件模版，因为不是相等target关系，所以要改模版，因此选择最右插入位置；
  • 不过在这题里，这个思路是不对的，因为这样的复杂度O(N * NlogN)，完全没必要。BF才只有O(N^2)；
  • 思路有问题，复杂度高是因为每次都要对subarray做sort。因此需要找到一个办法可以节约这部分。

TLE

• 使用一个treemap，从左到右，慢慢往里面添加元素，元素是排序好的
• 每次添加的那个即为已知条件里的j，已经添加进去的即为可选择的i
• 因此对于循环体内的部分，题目的思路调整为:在有序序列中寻找最右插入位置，套用模版即可
• 这样也就是在直觉解法的基础上节约出了sort的复杂度；

AC

代码

//寻找最右插入位置
lass Solution {
    public int solve(int[] nums) {
        int res = 0;
        if(nums.length == 0) return res;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(nums[0], 1);
        for(int i = 1;i < nums.length;i++){
            List<Integer> keys = new ArrayList<>(map.keySet());
            int boundary = binarySearch(keys, 3 * nums[i]);
            List<Integer> values = new ArrayList<>(map.values());
            for(int j = boundary;j < values.size();j++){
                res += values.get(j);
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
        }

        return res;
    }

    public int binarySearch(List<Integer> nums, int target){
        int left = 0, right = nums.size() - 1;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums.get(mid) > target){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

复杂度

time: O(NlogN),遍历N个元素，每个元素需要插入treemap，开销O(logN)，二分，开销O(logN)。总和还是O(NlogN)。 space: O(N)，需要常数个List以及TreeMap。

[yachtcoder]

Sorted List + Binary search O(nlgn), O(n)

class Solution:
    def solve(self, nums):
        sl = SortedList()
        ret = 0
        for n in nums:
            idx = sl.bisect_right(n*3)
            ret += len(sl) - idx
            sl.add(n)
        return ret

[ZacheryCao]

Idea:

Binary search and sorted list of scanned elements.

Code:

from sortedcontainers import SortedList
class Solution:
    def solve(self, nums):
        dp =  SortedList()
        ans = 0
        for i in nums:
            idx = bisect.bisect_right(dp, i * 3)
            ans += len(dp) - idx
            dp.add(i)
        return ans

Complexity:

Time: O(NlogN) Sapce: O(N)

[RocJeMaintiendrai]

题目

Given a list of integers nums, return the number of pairs i < j such that nums[i] > nums[j] * 3.

思路

参考官方题解

代码

class Solution:
    def solve(self, A):
        d = SortedList()
        res = 0

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

复杂度分析

时间复杂度

O(nlogn)

空间复杂度

O(n)

[st2yang]

思路

• SortedList + bisect

代码

• python

  
  from sortedcontainers import SortedList

class Solution: def solve(self, A): d = SortedList() res = 0

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

## 复杂度
- 时间: O(nlogn)
- 空间: O(n)

[chenming-cao]

解题思路

参考官方题解和楼下的luojiamun的题解。使用二分法。遍历数组，用TreeMap储存已经遍历过的元素和元素出现的个数，用tailMap(K fromKey, boolean inclusive)寻找所有满足条件（大于当前元素的三倍）的Key-Value pairs。然后将value的总和加到结果中。全部遍历结束后返回结果。

代码

class Solution {
    public int solve(int[] nums) {
        if (nums.length == 0) return 0;
        int res = 0;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(nums[0], 1);
        for (int i = 1; i < nums.length; i++) {
            Map<Integer, Integer> candidates = map.tailMap(3 * nums[i], false);
            for (Map.Entry<Integer, Integer> entry: candidates.entrySet()) {
                res += entry.getValue();
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        return res;        
    }
}

复杂度分析

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

[laofuWF]

class Solution:
    def solve(self, nums):
        sorted_list = SortedList()
        res = 0

        for n in nums:
            index = sorted_list.bisect_right(n * 3)
            res += len(sorted_list) - index
            sorted_list.add(n)

        return res

[HackBL]

class Solution {
    public int reversePairs(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = res + i - rightInsert(list, nums[i] * 2L);
            list.add(rightInsert(list, nums[i]), nums[i]);
        }
        return res;
    }

    public int rightInsert(List<Integer> list, long target) {
        int l = 0, r = list.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (list.get(mid) <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

[ginnydyy]

Problem

https://binarysearch.com/problems/Triple-Inversion

Notes

• Merge sort

  • Brute force costs O(n^2). Need to use some tricks based on merge sort to optimize the solution.
  • During the merge process of the merge sort, count the pairs that meets the requirement nums[i] > 3 * nums[j].
  • In the merge process, the left sub array and right sub array are sorted, and the indices of the elements in the right sub array j are greater than the indices of the elements in the left sub array i.
  • Compare each element at i with the element at j, if they meet the requirement, then incremenet the count. Since the sub arrays are sorted, if i and j meet the requirement, then elements from i to mid pairing with the elemnt j meet the requirement as well. So increment count with mid - i + 1.
  • Other process would stay the same as the normal merge sort.
  • If new a new temp array for each merge, the space complexity would be O(nlogn). To optimize it, always use one temp array, and reset it with all zeros after copying back the nums array. The space complexity can be reduced to O(n).

• Binary search

  • Iterate the nums, and try to find the matching elements to form pairs from the previous elements.
  • It requires the previous elements are sorted, so that can find the marching elements to form pairs reasonably.
  • If using common sorting methods to sort the previous elements, i.e. quick sort/merge sort, the sorting costs O(nlogn), then the overall solution costs O(n*nlogn) => O(n^2). It's the same as the brute force solution.
  • So need to use a TreeMap to maintain the previous elements, key is the element, value is the times that key appears in the nums. For each added key-value pair, TreeMap maintains the keys sorted with O(logn) cost.
  • Use binary search to find the first matching element from the previous elements => find the left most matching key from the TreeMap keys. Cost O(logn).
  • The target for the binary search is > 3 * current element. If it can be found, then all the keys after this boundary meet the requirement. Increment the count by the value of each key (the appearing times of the key in the nums).

Solution

• Merge sort

  
  import java.util.*;

class Solution { int count = 0;

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

private void mergeSort(int[] nums, int start, int end, int[] temp){
    if(start >= end){
        return;
    }

    int mid = start + (end - start) / 2;
    mergeSort(nums, start, mid, temp);
    mergeSort(nums, mid + 1, end, temp);
    merge(nums, start, mid, end, temp);
}

private void merge(int[] nums, int start, int mid, int end, int[] temp){
    int i = start;
    int j = mid + 1;
    int k = start;

    // count the pairs
    while(i <= mid && j <= end){
        if(nums[i] > 3 * nums[j]){
            count += mid - i + 1;
            j++;
        }else{
            i++;
        }
    }

    // merge for merge sort
    i = start;
    j = mid + 1;
    while(i <= mid && j <= end){
        if(nums[i] < nums[j]){
            temp[k] = nums[i];
            k++;
            i++;
        }else{
            temp[k] = nums[j];
            k++;
            j++;
        }
    }

    while(i <= mid){
        temp[k] = nums[i];
        k++;
        i++;           
    }

    while(j <= end){
        temp[k] = nums[j];
        k++;
        j++;
    }

    for(int p = start; p <= end; p++){
        nums[p] = temp[p];
    }
    Arrays.fill(temp, 0);
}

}

- Binary search
```java
import java.util.*;

class Solution {
    public int solve(int[] nums) {
        if(nums == null || nums.length < 2){
            return 0;
        }
        int count = 0;
        Map<Integer, Integer> map = new TreeMap<>();
        map.put(nums[0], 1);
        for(int i = 1; i < nums.length; i++){
            List<Integer> keys = new ArrayList<>(map.keySet());
            int boundary = binarySearch(keys, 3 * nums[i]);
            for(int j = boundary; j >=0 && j < keys.size(); j++){
                count += map.get(keys.get(j));
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        return count;
    }

    // use binary search to find the first element that > target
    // if it's found, return the index
    // otherwise, return -1
    private int binarySearch(List<Integer> list, int target){
        int start = 0;
        int end = list.size() - 1;
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            if(list.get(mid) > target){
                end = mid;
            }else if(list.get(mid) < target){
                start = mid;
            }else{
                start = mid;
            }
        }
        if(list.get(start) > target){
            return start;
        }
        if(list.get(end) > target){
            return end;
        }
        return -1;
    }
}

Complexity

• Merge sort
  • Time: O(nlogn) for merge sort (n is the size of nums).
  • Space: O(n) for the temp array. After optimization using only one temp array.
• Binary search
  • Time: O(nlogn). O(logn) for adding each element to the TreeMap. O(logn) for each binary search, each element in the nums requires one binary search operation. So O(nlogn).
  • Space: O(n) for the TreeMap.

[akxuan]

用bisect_right可以得到在sorted list 中小于等于某个值的个数, 对每个数循环即可 时间复杂度 nlogn 空间复杂度: n

class Solution:
    def solve(self, nums):
        d = SortedList()
        res = 0

        for a in nums:
            i = d.bisect_right(a * 3)
            res += len(d) - i
            d.add(a)
        return res

[yingliucreates]

link:

https://binarysearch.com/problems/Triple-Inversion

brute force 哈哈

代码 Javascript

function tripleInversion(nums) {
  if (!nums.length || nums.length === 1) return 0;
  let count = 0;
  while (nums.length > 1) {
    let last = nums.pop();
    let tripleLast = last * 3;
    for (let el of nums) {
      if (el > tripleLast) count++;
    }
  }
  return count;
}

复杂度分析

time: O（n^2） space: O（1）

[qyw-wqy]

class Solution {
    public int reversePairs(int[] nums) {
        long[] temp = new long[nums.length];
        for (int i = 0; i < nums.length; i++) {
            temp[i] = (long)nums[i];
        }
        return helper(temp, 0, nums.length-1);
    }

    private int helper(long[] nums, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int res = helper(nums, left, mid) + helper(nums, mid + 1, right);
        long[] merge = new long[right - left + 1];
        int l = left;
        int r = mid+1;
        // count the pair;
        while (r <= right) {
            while (l <= mid && nums[l] <= 2 * nums[r]) l++;
            res += mid - l + 1;
            r++;
        }

        l = left;
        r = mid+1;
        int p = 0;
        // merge sort;
        while (l <= mid || r <= right) {
            if (r > right || (l <= mid && nums[l] < nums[r])) {
                merge[p++] = nums[l++];
            } else {
                merge[p++] = nums[r++];
            }
        }
        // copy back
        for (int i = 0; i < merge.length; i++) {
            nums[left+i] = merge[i];
        }

        return res;
    }
}

Time: O(NlogN)\ Space: O(N)

[kidexp]

thoughts

看的官方题解用了SortedList这个data structure，但是不在标准python 库里面

code

from typing import List

from sortedcontainers import SortedList

class Solution:
    def solve(self, nums: List[int]):
        d = SortedList()
        ans = 0

        for num in nums:
            i = d.bisect_right(num * 3)
            ans += len(d) - i
            d.add(num)
        return ans

complexity

time O(nlgn)

space O(n)

[tongxw]

思路

考察是否理解mergesort的过程 mergesort先把数组所有元素分成独立的一组，最后merge的时候从单个元素开始合并有序数组，这个过程中同时可以找逆序对。

代码

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

        return count;
    }

    private void mergeSort(int[] nums, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid, temp);
        mergeSort(nums, mid+1, end, temp);
        merge(nums, start, mid, end, temp);
    }

    private void merge(int[] nums, int start, int mid, int end, int[] temp) {
        int i = start;
        int j = mid + 1;
        int idx = 0;
        while (i <= mid && j<= end) {
            if (nums[i] < nums[j]) {
                temp[idx++] = nums[i++];
            } else {
                temp[idx++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[idx++] = nums[i++];
        }
        while (j <= end) {
            temp[idx++] = nums[j++];
        }

        // check inversitoin paris
        checkInversionPairs(nums, start, mid, end);

        // update array
        i = start;
        idx = 0;
        while (i <= end) {
            nums[i++] = temp[idx++];
        }
    }

    private void checkInversionPairs(int[] nums, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        while (i <= mid && j <= end) {
            if (nums[i] > nums[j] * 3) {
                count += mid - i + 1;
                j++;
            } else {
                i++;
            }
        }
    }
}

TC: O(nlogn) SC: O(n)

[mmboxmm]

思路

看起来只有利用mergeSort顺序对，逆序对的特性达到nlongn的复杂度了。

代码

fun solve(nums: IntArray): Int = mergeSort(nums)

fun mergeSort(nums: IntArray, tmp: IntArray =  IntArray(nums.size), start: Int = 0, end: Int = nums.lastIndex): Int {
  if (start >= end) return 0
  val mid = (start + end) ushr 1
  var res = 0
  res += mergeSort(nums, tmp, start, mid)
  res += mergeSort(nums, tmp, mid + 1, end)
  res += merge(nums, tmp, start, mid, end)
  return res
}

fun merge(nums: IntArray, tmp: IntArray, start: Int, mid: Int, end: Int): Int {
  var res = 0
  var r = mid + 1

  for (l in start..mid) {
    if (nums[l] > nums[r] * 3) {
      res += end - r + 1
    } else {
      r++
    }
  }

  var i = start
  var l = start
  r = mid + 1

  while (l <= mid && r <= end) {
    if (nums[l] >= nums[r]) {
      tmp[i++] = nums[l++]
    } else {
      tmp[i++] = nums[r++]
    }
  }
  while (l <= mid) tmp[i++] = nums[l++]
  while (r <= end) tmp[i++] = nums[r++]
  (start..end).forEach { nums[it] = tmp[it] }

  return  res
}

复杂度

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

[Huangxuang]

题目：493. Reverse Pairs

思路

• 暴力解On^2

代码

class Solution {
    public int reversePairs(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > 2 * nums[j]) {
                    res++;
                }
            }
        }
        return res;

• 思路二

归并排序 思路及解法

在归并排序的过程中，假设对于数组 \textit{nums}[l..r]nums[l..r] 而言，我们已经分别求出了子数组 \textit{nums}[l..m]nums[l..m] 与 \textit{nums}[m+1..r]nums[m+1..r] 的翻转对数目，并已将两个子数组分别排好序，则 \textit{nums}[l..r]nums[l..r] 中的翻转对数目，就等于两个子数组的翻转对数目之和，加上左右端点分别位于两个子数组的翻转对数目。

我们可以为两个数组分别维护指针 i,ji,j。对于任意给定的 ii 而言，我们不断地向右移动 jj，直到 \textit{nums}[i] \le 2\cdot \textit{nums}[j]nums[i]≤2⋅nums[j]。此时，意味着以 ii 为左端点的翻转对数量为 j-m-1j−m−1。随后，我们再将 ii 向右移动一个单位，并用相同的方式计算以 ii 为左端点的翻转对数量。不断重复这样的过程，就能够求出所有左右端点分别位于两个子数组的翻转对数目。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/reverse-pairs/solution/fan-zhuan-dui-by-leetcode-solution/

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;
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reverse-pairs/solution/fan-zhuan-dui-by-leetcode-solution/

复杂度分析

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

[wangzehan123]

Java

class Solution {
    public int reversePairs(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = res + i - rightInsert(list, nums[i] * 2L);
            list.add(rightInsert(list, nums[i]), nums[i]);
        }
        return res;
    }

    public int rightInsert(List<Integer> list, long target) {
        int l = 0, r = list.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (list.get(mid) <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

[pophy]

思路

• merge sort变种题
  • 归并的时候检查 nums[l] > nums[r] * 3，如果成立则count += mid - l + 1

Java Code

class Solution {
    private int count;
    public int solve(int[] nums) {
        count = 0;
        sort(nums, 0, nums.length - 1);
        return count;
    }

    private void sort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        sort(nums, start, mid);
        sort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int[] temp = new int[nums.length];
        int l = start, r = mid + 1, cur = start;
        while (l <= mid && r <= end) {
            if (nums[l] <= nums[r]) {
                temp[cur++] = nums[l++];
            } else {
                temp[cur++] = nums[r++];
            }
        }
        while (l <= mid) {
            temp[cur++] = nums[l++];
        }
        while (r <= end) {
            temp[cur++] = nums[r++];
        }
        l = start; r = mid + 1;
        while (l <= mid && r <= end) {
            if (nums[l] <= nums[r] * 3) {
                l++;
            } else {
                count += mid - l + 1;
                r++;
            }
        }
        for (int i = start; i <= end; i++) {
            nums[i] = temp[i];
        }
    }
}

时间&空间

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

[septasset]

代码(Python)

class Solution:
    def solve(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] <=  3 * 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

[AgathaWang]

二分法

tc: O(nlogn)

class Solution:
    def solve(self, nums):
        d = SortedList()
        ans = 0

        for a in nums:
            i = d.bisect_right(a * 3)   # 已遍历的数小于a*3的最大index
            ans += len(d) - i  # 已遍历的数中大于a*3的数的个数
            d.add(a)
        return ans

[ghost]

题目

762.Number Stream to Intervals

思路

Merge Sort

代码

class Solution:
    def solve(self, nums):
        self.cnt = 0
        self.merge_sort(nums, 0, len(nums)-1, [])

        return self.cnt

    def merge(self, 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

        m, n = start, mid+1

        while (m <= mid and n<=end):
            if nums[m] <= nums[n] * 3:
                m+=1
            else:
                self.cnt += mid-m+1
                n+=1

        while(i<=mid):
            temp.append(nums[i])
            i+=1
        while(j<=end):
            temp.append(nums[j])
            j+=1

        nums[start:start+len(temp)] = temp
        temp.clear()

        return self.cnt

    def merge_sort(self, nums, start, end, temp):
        if start >= end: return
        mid = (start+end)//2

        self.merge_sort(nums, start, mid, temp)
        self.merge_sort(nums, mid+1, end, temp)
        self.merge(nums, start, mid, end, temp)

复杂度

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

[BlueRui]

Problem 493. Reverse Pairs

Algorithm

• We will apply merge sort to solve this problem.
• Let T(i, j) represent the problem of reverse pairs from i to j. Then we can partition it as follows: T(i, j) = T(i, m) + T(m+1, j) + C, where m=(i+j)/2, and C is the additional operations to combine to two subproblem.
• In this case, C is the problem of finding number of reverse pairs where i is from the first partition and j is from the second partition, such that nums[i] > 2nums[j]*.
• Also, both partitions are already naturally sorted in the merge process.

Complexity

• Time Complexity: O(NlogN). This is the same as a standard merge sort. The merge step takes O(N) to sort each partition and O(N) to solve for C. We have O(logN) recursive calls.
• Space Complexity: O(N). This is the extra space for the helper array.

Code

Language: Java

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

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

    // The relative order within the first half and second half no longer matters now
    // We only need to find i from first half and j from second half, such that nums[i] > 2*nums[j]
    int p1 = left;
    int p2 = mid + 1;
    while (p1 <= mid && p2 <= right) {
        if (nums[p1] / 2.0 > nums[p2]) {
            count += mid - p1 + 1;
            p2++;
        } else {
            p1++;
        }
    }
    merge(nums, helper, left, mid, right);
    return count;
}

private void merge(int[] nums, int[] helper, int left, int mid, int right) {
    // Merge sort left to right
    for (int i = left; i <= right; i++) {
        helper[i] = nums[i];
    }
    int p1 = left;
    int p2 = mid + 1;
    while (p1 <= mid && p2 <= right) {
        if (helper[p1] <= helper[p2]) {
            nums[left++] = helper[p1++];
        } else {
            nums[left++] = helper[p2++];
        }
    }
    while (p1 <= mid) {
        nums[left++] = helper[p1++];
    }
}

[ai2095]

Triple Inversion

https://binarysearch.com/problems/Triple-Inversion

Topics

• sort

Similar Questions

Hard

Medium

思路

binary search

代码 Python

class Solution:
    def solve(self, nums):
        def bin_se(i):
            nonlocal tmp_nums
            l, r = 0, i-1
            while l <= r:
                mid = l + (r-l)//2
                if tmp_nums[mid][0] * 3 >= tmp_nums[i][0]:
                    r = mid -1
                else:
                    l = mid + 1
            return r

        tmp_nums = [(num, i) for i, num in enumerate(nums)]
        tmp_nums.sort(key= lambda e: e[0])

        result = 0
        for indx in range(len(tmp_nums)-1, -1, 0):
            tmp_i = bin_se(indx)
            cur_num, cur_i = tmp_nums[indx]
            for j in range(tmp_i):
                num, i = tmp_nums[j]
                if cur_i < i:
                    result += 1
        return result

复杂度分析

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

[Laurence-try]

思路

有一定难度，看了很久决定参考官方解答

代码

使用语言：Python3

class Solution:
    def solve(self, nums):
        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] <=  3 * 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

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

[carsonlin9996]

思路

merge sort, 参考官方答案

语言

java

import java.util.*;

class Solution {
    int cnt = 0;
    public int solve(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(0, nums.length - 1, nums, temp);

        return cnt;
    }

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

        merge(start, end, nums, temp);

    }

    private void merge(int start, int end, int[] nums, int[] temp) {
        int left = start;
        int mid = start + (end - start) / 2;
        int right = mid + 1;
        int tempIndex = start;

        while (left <= mid && right <= end) {
            if (nums[left] < nums[right]) {
                temp[tempIndex++] = nums[left++];
            } else {
                temp[tempIndex++] = nums[right++];
            }
        }

        int i = start;
        int j = mid + 1;

        while (i <= mid && j <= end) {
            if (nums[i] <= nums[j] * 3) {
                i++;
            } else {
                cnt += mid - i + 1;
                j++;
            }
        }

        while (left <= mid) {
            temp[tempIndex++] = nums[left++];
        }
        while (right <= end) {
            temp[tempIndex++] = nums[right++];
        }

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

[ZiyangZ]

• Second time solving this problem.
• Took quite a while to remember all the details.
• Time O(nlogn) space O(n).

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

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

    public void merge(int[] nums, int left, int mid, int right) {
        int a = left;
        int b = mid + 1;
        while (a <= mid && b <= right) {
            if ((long) nums[a] > (long) 3 * nums[b]) {
                count += mid - a + 1;
                b++;
            } else a++;
        }

        int[] temp = new int[right - left + 1];
        a = left;
        b = mid + 1;
        int i = 0;
        while (a <= mid && b <= right) {
            if (nums[a] < nums[b]) {
                temp[i] = nums[a];
                a++;
            } else {
                temp[i] = nums[b];
                b++;
            }
            i++;
        }

        while (a <= mid) temp[i++] = nums[a++];
        while (b <= right) temp[i++] = nums[b++];
        for (i = left; i <= right; i++) {
            nums[i] = temp[i - left];
        }
    }
}

[BpointA]

思路

二分法，利用bisect_right和insort_right实现（参考讲义解法）

Python代码

class Solution:
    def solve(self, nums):
        cnt=0
        arr=[]
        for i in nums:
            right=bisect_right(arr,i*3)
            cnt+=len(arr)-right
            insort_right(arr,i)
        return cnt

复杂度

时间复杂度：O(nlogn)，bisect n次

空间复杂度：O(n)，d的长度

[watermelonDrip]

class Solution:
    def solve(self, nums):
        dp = []
        ans = 0
        for i in nums:
            idx = bisect.bisect_right(dp, i * 3)
            ans += len(dp) - idx
            bisect.insort(dp, i)
        return ans

[KennethAlgol]

class Solution {
    public int reversePairs(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = res + i - rightInsert(list, nums[i] * 2L);
            list.add(rightInsert(list, nums[i]), nums[i]);
        }
        return res;
    }

    public int rightInsert(List<Integer> list, long target) {
        int left = 0, right = list.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

[wangyifan2018]

class Solution:
    def find_reversed_pairs(self,nums,left,right):
        res,mid = 0,(left+right)//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(self,nums,nums_sorted,l,r):
        if l >= r: return 0
        mid = (l+r) // 2
        res = self.merge_sort(nums,nums_sorted,l,mid) +\
              self.merge_sort(nums,nums_sorted,mid+1,r) +\
              self.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

    def reversePairs(self, nums: List[int]) -> int:
        if not nums: return 0
        nums_sorted = [0] * len(nums)
        return self.merge_sort(nums,nums_sorted,0,len(nums)-1)

[wenlong201807]

代码块

var countPrimeSetBits = function (L, R) {
  let count = 0;
  let isPrime = (num) => {
    if (num === 0 || num === 1) {
      return false;
    } else if (num === 2) {
      return true;
    } else {
      for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) {
          return false;
        }
      }
      return true;
    }
  };
  for (let i = L; i <= R; i++) {
    let oneLen = i.toString(2).replace(/0/g, '').length;
    isPrime(oneLen) && count++;
  }
  return count;
};

时间复杂度和空间复杂度

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

[ZJP1483469269]

思路

二分 构造有序列表并维护

代码

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        if(nums.length<2)return 0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int ans = 0;
        for(int i = 1;i<nums.length;i++){
            int b = indexofright(list,nums[i]*3);
            ans += (list.size() - b);
            int c = indexofright(list,nums[i]);
            list.add(c,nums[i]);
        }
        return ans;

    }
    public int indexofright(ArrayList<Integer> list,int a){
        int l = 0,r =list.size()-1;
        while(l<=r){
            int mid = l + (r - l) / 2;
            if(list.get(mid) <= a) l = mid +1;
            else r = mid -1; 
        }
        return l;
    }
}

复杂度分析

时间复杂度：O（logn^2） 空间复杂度：O（n）

[MoncozGC]

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        if(nums.length<2)return 0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int ans = 0;
        for(int i = 1;i<nums.length;i++){
            int b = indexofright(list,nums[i]*3);
            ans += (list.size() - b);
            int c = indexofright(list,nums[i]);
            list.add(c,nums[i]);
        }
        return ans;

    }
    public int indexofright(ArrayList<Integer> list,int a){
        int l = 0,r =list.size()-1;
        while(l<=r){
            int mid = l + (r - l) / 2;
            if(list.get(mid) <= a) l = mid +1;
            else r = mid -1; 
        }
        return l;
    }
}

[Poidaze7]

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

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

[lxy030988]

思路

• 暴力解法

代码 js

const numberStreamToIntervals = (nums) => {
  let sum = 0
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] > nums[j] * 3) {
        sum++
      }
    }
  }
  return sum
}

复杂度分析

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

[Daniel-Zheng]

思路

归并排序里加几行比较代码。

代码(C++)

class Solution {
public:
    int res = 0;
    void mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int mid = 0;
        if (l < r) {
            mid = l + (r - l) / 2;
            mergeSort(nums, l, mid);
            mergeSort(nums, mid + 1, r);
            merge(nums, l, mid, r);
        }
    }

    void merge(vector<int>& nums, int l, int mid, int r) {
        int lenLeft = mid - l + 1;
        int lenRight = r - mid;
        vector<int> left(lenLeft), right(lenRight);
        for (int i = 0; i < lenLeft; i++) left[i] = nums[l + i];
        for (int i = 0; i < lenRight; i++) right[i] = nums[mid + 1 + i];
        int i = 0, j = 0;
        int m = l;
        int n = mid + 1;

        while (m <= mid && n <= r) {
            if ((long long)nums[m] > (long long)nums[n] * 3) {
                res += mid - m + 1;
                n++;
            } else {
                m++;
            }
        }

        while (i < lenLeft && j < lenRight) {
            if ((long long)left[i] <= (long long)right[j]) {
                nums[l++] = left[i++];
            } else {
                nums[l++] = right[j++];
            }
        }
        while (i < lenLeft) nums[l++] = left[i++];
        while (j < lenRight) nums[l++] = right[j++];
    }

    int reversePairs(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return res;
    }
};

复杂度分析

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

[zol013]

两种解法： merge sort 在merge sort 过程中记录逆序对。 二分法： 创建新的Array d, 每次将nums中的数num插入d中时用二分查找找到 num*3的位置， ans 加上 数组长度减去这个位置的部分，然后将num有序的插入d中，把d初始为sortedlist 可以把time complexity 维持在O(nlogn) Python 3 code:

class Solution:
    def solve(self, nums):
        cnt = 0
        def merge(nums, start, mid, end, temp):
            nonlocal cnt
            i = start
            j = 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] <= 3 * nums[tj]:
                    ti += 1
                else:
                    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 cnt
        '''
class Solution:
    def solve(self, nums):
        d = []
        ans = 0

        for a in nums:
            i = bisect.bisect_right(d, a * 3)
            ans += len(d) - i
            bisect.insort(d, a)
        return ans
        '''

Time Complexity: O(nlog(n)) Space Complexity: O(n)

[Moin-Jer]

思路

---

遍历的过程中构造有序数组，二分查找比当前元素 * 3 大的元素

代码

---

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int ans = 0;
        for (int n : nums) {
            int idnex = find(list, n * 3);
            ans += list.size() - idnex;
            list.add(find(list, n), n);
        }
        return ans;
    }

    private int find(List<Integer> list, int n) {
        int l = 0, r = list.size() - 1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (list.get(mid) <= n) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

复杂度分析

---

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

[shamworld]

思路

• 暴力法超出时间限制

  var reversePairs = function(nums) {
  let res = 0;
  for(let i = 0; i < nums.length; i++){
      for(j = i+1; j < nums.length; j++){
          if(nums[i]>nums[j]*3){
              res++;
          }
  
      }
  }
  
  return res;
  };

• 抄下

  
  class Solution:
  def solve(self, A):
      d = SortedList()
      ans = 0
  
      for a in A:
          i = d.bisect_right(a * 3)
          ans += len(d) - i
          d.add(a)
      return ans

[xyinghe]

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

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

[watchpoints]

参考官方思路 翻译java

class Solution {
   public int reversePairs(int[] nums) {
        if(nums == null || nums.length < 2) {
            return 0;
        }
        return sort(nums, 0, nums.length - 1);
    }

    private int sort(int[] nums, int L, int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + (R - L) / 2;
        return  sort(nums, L, mid) +
                sort(nums, mid + 1, R) +
                merge(nums, L, mid, R);
    }

    private int merge(int[] nums, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int p1 = L;
        int p2 = mid + 1;
        int res = 0;
        int i = 0;
        //计算翻转对
        while (p1 <= mid && p2 <= R) {
            if (nums[p1] > 2 * (long) nums[p2]) {
                res += mid - p1 + 1;
                p2++;
            } else {
                p1++;
            }
        }
        //归位还要继续使用
        p1 = L;
        p2 = mid + 1;
        while (p1 <= mid && p2 <= R) {
            help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= mid) {
            help[i++] = nums[p1++];
        }
        while (p2 <= R) {
            help[i++] = nums[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            nums[L + j] = help[j];
        }
        return res;
    }
}

[liuyangqiQAQ]

二分查找。由于只需要找i < j 。所以维护一个有序链表即可

class Solution {

    public int solve(int[] nums) {
        if(nums.length == 0) return 0;
        //由于数据从左到右。所以我们只需要维护一个有序的连表
        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int sum = 0;
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            //查找满足条件的
            int index = binarySearch(num * 3, list);
            sum += list.size() - index;
            //插入指定位置
            int insert = binarySearch(num, list);
            list.add(insert, num);
        }
        return sum;
    }

    public int binarySearch(int num, List<Integer> list) {
        //查找比num小于的数值
        int left = 0, right = list.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if(list.get(mid) <= num) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return list.get(right) <= num ? list.size(): right;
    }
}

[xieyj17]

class Solution:
    def solve(self, nums):
        d = []
        res = 0

        for n in nums:
            i = bisect.bisect_right(d, n*3)
            res += len(d) - i
            bisect.insort(d, n)

        return res

照着讲义里面的标准答案写的，其实我自己还没有搞明白

Space: O(N)

Time: O(NlogN)

[hewenyi666]

题目名称

762. 二进制表示中质数个计算置位

题目链接

https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/

题目思路

根据数据范围10的六次方，所以直接记录二十以内的质数就可以

code for Python3

class Solution:
    def countPrimeSetBits(self, L: int, R: int) -> int:
        zhi = [0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1]
        n=0
        for i in range(L,R+1):
            q=bin(i)
            s=q.count('1')
            if zhi[s]==1:
                n+=1
        return n

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[biancaone]

class Solution:
    def solve(self, nums):
        arr = []
        res = 0
        for i in nums:
            idx = bisect.bisect_right(arr, i * 3)
            res += len(arr) - idx
            bisect.insort(arr, i)
        return res