【Day 39 】2022-01-19 - 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)

[yan0327]

493. 翻转对 https://leetcode-cn.com/problems/reverse-pairs/ 思路： 分治思想实现排序对

func reversePairs(nums []int) int {
    if len(nums) <= 1{
        return 0
    }
    n := len(nums)
    l1 := append([]int{},nums[:n/2]...)
    l2 := append([]int{},nums[n/2:]...)
    count := reversePairs(l1) + reversePairs(l2)
    l := 0
    for _,v := range l1{
        for l<len(l2)&&v > 2*l2[l]{
            l++
        }
        count += l
    }
    p1,p2 :=0,0
    for i := range nums{
        if p1 < len(l1)&&(p2 == len(l2)||l1[p1]<l2[p2]){
            nums[i] = l1[p1]
            p1++
        }else{
            nums[i] = l2[p2]
            p2++
        }
    }
    return count

}

时间复杂度：O（NlogN） 空间复杂度：O（N）

[MonkofEast]

000. Number Stream to Intervals

Click Me

Algo

1. Sometimes u can construct a sorted list urself.

Code

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

Comp

T: O(nlogN)

S: O(N)

[feifan-bai]

思路 1.分治法

代码

class Solution:
    def solve(self, nums):
        self.cnt = 0
        def merge(nums, start, mid, end, tmp):
            i, j = start, mid+1
            while i <= mid and j <= end:
                if nums[i] <= nums[j]:
                    tmp.append(nums[i])
                    i += 1
                else:
                    tmp.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:
                tmp.append(nums[i])
                i += 1
            while j <= end:
                tmp.append(nums[j])
                j += 1
            for i in range(len(tmp)):
                nums[start + i] = tmp[i]
            tmp.clear()

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

复杂度分析

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

[laofuWF]

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

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

        return res

    def find_index(self, sorted_list, n):
        # if not sorted_list:
        #     return 0

        left = 0
        right = len(sorted_list)

        while left < right:
            mid = left + (right - left) // 2

            if n < sorted_list[mid]:
                right = mid
            else:
                left = mid + 1

        return left

[tongxw]

思路

归并排序过程中找逆序对

class Solution {
    int count = 0;
    public int reversePairs(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);

        // nums[start:mid] 和 nums[mid+1:end] 都是有序数组
        // 且 start:mid的所有索引i，在原数组中，都大于mid+1:end的所有索引j
        // 此时可以根据题意统计逆序对
        int i = start;
        int j = mid + 1;
        while (i <= mid && j <= end) {
            if ((long)nums[i] <= (long)2 * nums[j]) {
                i++;
            } else {
                // nums[i] > 2 * nums[j]
                // 因为nums[start:mid]有序，所以此时nums[i:mid]所有数字都大于2*nums[j]
                count += mid - i + 1;
                j++;
            }
        }

        // 继续进行mergeSort
        i = start;
        j = mid + 1;
        int k = 0;
        while (i<=mid && j<=end) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i<=mid) {
            temp[k++] = nums[i++];
        }
        while (j<=end) {
            temp[k++] = nums[j++];
        }

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

TC: O(NLogN) SC: O(N)

[ZacheryCao]

Idea

Divide and Conquer

Code

class Solution:
    def solve(self, nums):
        return self.mergeSort(nums, 0, len(nums)-1, [0]*len(nums))

    def merge(self, nums, s, m, e, helper):
        i = s
        while i <= e:
            helper[i] = nums[i]
            i+=1
        p1 = s
        p2 = m + 1
        p3 = s
        while p1 <= m and p2<=e:
            if helper[p1] < helper[p2]:
                nums[p3] = helper[p1]
                p1 += 1
            else:
                nums[p3] = helper[p2]
                p2+=1
            p3 += 1
        while p1<=m:
            nums[p3]=helper[p1]
            p1+=1
            p3+=1
        while p2<=e:
            nums[p3]=helper[p2]
            p2+=1
            p3+=1

    def mergeSort(self, nums, s, e, helper):
        if s>=e:
            return 0
        mid = (e+s)//2
        cnt = self.mergeSort(nums, s, mid, helper) + self.mergeSort(nums, mid + 1, e,helper)
        i, j = s, mid+1
        while i <= mid and j <= e:
            if nums[i]<=3 * nums[j]:
                i+=1
            else:
                cnt +=  mid -i+ 1
                j += 1
        self.merge(nums, s, mid, e, helper)
        return cnt

Complexity:

Time: O(N log N) Space;O(N)

[chakochako]

if lo < 0:
    raise ValueError('lo must be non-negative')
if hi is None:
    hi = len(a)
while lo < hi:
    mid = (lo+hi)//2
    if a[mid] < x: lo = mid+1
    else: hi = mid
a.insert(lo, x)
Implementation of bisect_right:

if lo < 0:
    raise ValueError('lo must be non-negative')
if hi is None:
    hi = len(a)
while lo < hi:
    mid = (lo+hi)//2
    if x < a[mid]: hi = mid
    else: lo = mid+1
return lo
class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        comp = []
        count = 0
        for i in range(len(nums)):
            insInd = bisect_right(comp, 3 * nums[i])
            count += len(comp) - insInd
            insort(comp, nums[i])
        return count

[LeahLuo0903]

class Solution { public: int countPrimeSetBits(int L, int R) { int count=0; for(int i=L;i<=R;i++){ if(checkPrime(findSetBits(i))) count++; } return count; } int findSetBits(int n){ int count=0; while(n){ n=n&(n-1); count++; } return count; } bool checkPrime(int x){ return (x == 2 || x == 3 || x == 5 || x == 7 || x == 11 || x == 13 || x == 17 || x == 19); } };

[CodeWithIris]

Question

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

Note (Merge sort)

Solution (C++)

int mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    int res = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
    int i = left, j = mid + 1;
    while (i <= mid) {
        while (j <= right && nums[i] > 3.0 * nums[j]) ++j;
        res += (j - mid - 1);
        ++i;
    }
    sort(nums.begin() + left, nums.begin() + right + 1);
    return res;
}
int solve(vector<int>& nums) {
    if (nums.empty()) return 0;
    return mergeSort(nums, 0, nums.size() - 1);  
}

Complexity

• T: O(nlogn)
• S: O(n)

[wangzehan123]

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        List<Integer> list = new ArrayList();
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            int where = find(list, nums[i] * 3);
            ret += list.size() - where;
            list.add(find(list, nums[i]), nums[i]);
        }
        return ret;
    }
    public int find(List<Integer> list, int find) {
        int l = 0;
        int r = list.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (list.get(mid) > find) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

[CoreJa]

思路

看了hint才做出来的，一开始根本没想到归并排序，归并排序YYDS。

• 朴素暴力法：$O(n^2)$，直接双重循环就行，TLE
• 二分法：$O(n^2)$，朴素暴力法改进得到，如果内层循环的查找是在一个有序列表中进行，就并不需要$O(n)$才能找到，而是可以用二分法做到$O(\log n)$，所以在外层遍历的同时构建一个有序列表。但这里构建有序列表要涉及到移动数组，插入的复杂度仍然为$O(n)$，所以总复杂度依然是$O(n*(n+\log n))=O(n^2)$，但是BS上勉强能过(py黑魔法出现了)。
• 二分法+平衡二叉树：$O(n\log n)$，继续优化上面的方案，结合平衡二叉树来保证有序列表的插入复杂度能降低到$O(\log n)$，总复杂度为$O(n*(\log n+\log n))=O(n\log n)$

• 归并排序：$O(n\log n)$，这个题目出题人的意图解法，将数组分为前后两部分，对这两部分递归调用自己排序(可以理解为已经有序了)，合并的时候因为两部分已经有序了，可以在$O(n)$时间内算出满足条件的个数。

  代码

  class Solution:
  # 朴素暴力法：$O(n^2)$，直接双重循环就行，TLE
  def solve1(self, nums):
      cnt = 0
      n = len(nums)
      for i in range(n):
          for j in range(i, n):
              if nums[i] > nums[j] * 3:
                  cnt += 1
      return cnt
  
  # 二分法：$O(n^2)$，朴素暴力法改进得到，如果内层循环的查找是在一个**有序列表**中进行，就并不需
  # 要$O(n)$才能找到，而是可以用二分法做到$O(\log n)$，所以在外层遍历的同时构建一个有序列表。
  # 但这里构建有序列表要涉及到移动数组，插入的复杂度仍然为$O(n)$，所以总复杂度依然是$O(n*(n+\log n))
  # =O(n^2)$，但是BS上勉强能过(`py`黑魔法出现了)。
  def solve2(self, nums):
      n = len(nums)
      nums_new = []
      cnt = 0
      for i in range(n - 1, -1, -1):
          cnt += bisect.bisect_left(nums_new, nums[i] / 3)
          bisect.insort_right(nums_new, nums[i])
      return cnt
  
  # 二分法+平衡二叉树：$O(n\log n)$，继续优化上面的方案，结合平衡二叉树来保证有序列表的插入复杂度能
  # 降低到$O(\log n)$，总复杂度为$O(n*(\log n+\log n))=O(n\log n)$
  def solve3(self, nums):
      nums_new = SortedList()
      cnt = 0
      for num in nums:
          cnt += len(nums_new) - nums_new.bisect_right(num * 3)
          nums_new.add(num)
      return cnt
  
  # 归并排序：$O(n\log n)$，这个题目出题人的意图解法，将数组分为前后两部分，对这两部分递归调用自己排序(可以
  # 理解为已经有序了)，合并的时候因为两部分已经有序了，可以在$O(n)$时间内算出满足条件的个数。
  def solve(self, nums):
      def merge(a, b):
          nonlocal cnt
          index = 0
          n = len(b)
          for num in a:
              while index < len(b):
                  if num > b[index] * 3:
                      cnt += n - index
                      break
                  index += 1
          ans = []
          i, j = 0, 0
          while i < len(a) and j < len(b):
              if a[i] > b[j]:
                  ans.append(a[i])
                  i += 1
              else:
                  ans.append(b[j])
                  j += 1
          ans += a[i:] if i < len(a) else b[j:]
  
          return ans
  
      def mergesort(nums):
          nonlocal cnt
          if len(nums) <= 1:
              return nums
          elif len(nums) == 2:
              if nums[0] > nums[1] * 3:
                  cnt += 1
              return [nums[1], nums[0]] if nums[1] > nums[0] else [nums[0], nums[1]]
          else:
              mid = len(nums) // 2
              return merge(mergesort(nums[:mid]), mergesort(nums[mid:]))
  
      cnt = 0
      mergesort(nums)
      return cnt

[Alexno1no2]

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

        for n in nums:            
            index = self.find_index_in_sorted_list(sorted_list,n * 3)
            res += len(sorted_list) - index

        return res

    def find_index_in_sorted_list(self, sorted_list, n):

        left = 0
        right = len(sorted_list) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if n < sorted_list[mid]:
                right = mid - 1
            else:
                left = mid + 1

        return left

if __name__ == '__main__':
    s = Solution()
    a=[7,1,2]
    print(s.solve(a))

[zwmanman]

class Solution: def solve(self, A): d = [] ans = 0

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

[ZJP1483469269]

class Solution:
    def solve(self, nums):
        def bsearch(ls,x):
            l , r = 0 , len(ls) - 1
            while l < r:
                mid = (l + r + 1) >> 1
                if ls[mid] <= x:
                    l = mid
                else:
                    r = mid - 1
            return l + 1 if ls[l] <= x else l
        ls = []
        if not len(nums):
            return 0
        ls.append(nums[0])
        res = 0
        for i in range(1,len(nums)):
            index = bsearch(ls,nums[i])
            resin = bsearch(ls,3 * nums[i])
            res += len(ls) - resin
            ls.insert(index,nums[i])

        return res

[shamworld]

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

[Tesla-1i]

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

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

        return res

    def find_index(self, sorted_list, n):
        # if not sorted_list:
        #     return 0

        left = 0
        right = len(sorted_list)

        while left < right:
            mid = left + (right - left) // 2

            if n < sorted_list[mid]:
                right = mid
            else:
                left = mid + 1

        return left

[chen445]

代码

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        result=0
        for num in range(left,right+1):
            if self.to_binary_bit(num):
                result+=1
        return result

    def to_binary_bit(self,num):
        prime=set([2,3,5,7,11,13,17,19,23])
        count=0
        while num !=0:
            if num%2 ==1:
                count+=1
            num=num//2
        if count in prime:
            return True
        else:
            return False 

[baddate]

归并排序

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] > 3*(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 solve(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)

[KevinWorkSpace]

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

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

    return res

def find_index(self, sorted_list, n):
    # if not sorted_list:
    #     return 0

    left = 0
    right = len(sorted_list)

    while left < right:
        mid = left + (right - left) // 2

        if n < sorted_list[mid]:
            right = mid
        else:
            left = mid + 1

    return left

[tangjy149]

思路

用归并排序，计算逆序数

代码

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return merge(nums,0,nums.size()-1);
    }
    int merge(vector<int>& nums,int left,int right){
        if(left==right) return 0;
        int mid=left+((right-left)>>1);
        int count=merge(nums,left,mid)+merge(nums,mid+1,right);
        int l=left,r=mid+1;
        while(l<=mid && r<=right){
            if((long long)nums[l]>(long long)3*nums[r]){
                r++;
                count+=(mid-l+1);
            }else{
                l++;
            }
        }
        inplace_merge(nums.begin()+left,nums.begin()+mid+1,nums.begin()+right+1);
        return count;
    }
};

[zjsuper]

class Solution: def solve(self, nums): if len(nums)<2: return 0 pairs = 0 if len(nums) == 2: if nums[1]*3 <nums[0]: return 1 else: return 0 for i in range(len(nums)-1): newlst = nums[i+1:] newlst.sort()

find target value, samller than target value

        target = nums[i]/3

        l = 0
        r = len(newlst)-1

        while l<r:
            mid = (l+r)//2
            if newlst[mid]>= target:
                r = mid-1
            elif newlst[mid] < target:
                # if mid == len(newlst)-1:
                #     pairs += mid+1
                #     break
                # elif newlst[mid+1] >= target:
                #     pairs += mid+1
                #     break
                # else:
                #     l = mid+1
                #     pairs += mid+1
                l = mid+1
        if newlst[l] < target:
            pairs += l+1
        elif newlst[l] >= target:
            pairs += l
    return pairs

[rzhao010]

Thoughts

Binary search + Merge sort

Code

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

    private int reversePairs(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = left + (right - left) / 2;
            int n1 = reversePairs(nums, left, mid);
            int n2 = reversePairs(nums, mid + 1, right);
            int res = n1 + n2;

            int i = left;
            int j = mid + 1;
            while (i <= mid) {
                while (j <= right && (long)nums[i] > 3 * (long)nums[j]) {
                    j++;
                }
                res += 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 res;
        }
    }
}

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

[junbuer]

思路

• 二分法

  代码

  class Solution:
  def solve(self, nums):
      sortlist = Sortedlist()
      cnt = 0
      for num in nums:
          cnt += len(sortlist) - sortlist.bisect_right(num * 3)
          sortlist.add(num)
      return cnt      

  复杂度分析

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

[xinhaoyi]

Triple Inversion

Question 757 of 1031

Triple Inversion | binarysearch

要梯子

题目

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)

错误的思路一

错误原因在于不允许排序，排序会改变数字顺序！！！

先逆序排序，也就是从大到小排序

对排序后的第一个数nums[0],我们只要用二分查找找到第一个满足nums[0] > 3*nums[i]的数

它之后的所有数都会满足这个条件，然后我们用count += nums.length - i即可

代码

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        /*
        //逆序排序，也就是从大到小排序
        //你这个写错了，只能排列Integer修饰的，不能排列int[]数组
        Arrays.sort(nums,Collections.reverseOrder());
        */
        //排序的正确写法应该是
        Arrays.sort(nums);
        for(int i = 0,j = nums.length - 1;i < j; i++, j--){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        //对排序后的第一个数nums[0],我们只要找到第一个满足nums[0] > 3*nums[i]的数
        //它之后的所有数都会满足这个条件，然后我们用count += nums.length - i即可
        int length = nums.length;
        //返回的结果count
        int count = 0;
        //上一轮找到的符合nums[0] > 3*nums[i]的i值，初始值为0
        int storeIndex = 0;
        for(int index = 0; index < length; index++){
            int left = storeIndex;
            int right = length - 1;
            while(left < right){
                int mid = left + (right - left) / 2;
                //如果不满足条件，去不包含mid的右区间继续找
                if(nums[index]<=3 * nums[mid]){
                    left = mid + 1;
                }
                //如果满足条件，去包含mid的左区间继续找
                else{
                    right = mid;
                }
            }
            //退出循环后left == right
            //如果就没有满足条件的，直接break，不用往后面找了
            if(nums[index]<=3 * nums[left]){
                break;
            }
            //反之满足条件
            storeIndex = left;
            count = count + length - storeIndex;
        }

        //最后返回count即可
        return count;
    }
}

思路二

维护一个从小到大顺序排列的辅助list，一开始list为空，我们去顺次遍历nums[]数组

把nums[i]3 带入到list中去用二分法查找第一个比nums[i] 3要大的数字，因为此时list中的数字

都是在原来的nums中要排在nums[i]前面的，所以一旦找到了这个数字的下标where

这个数字后面的所有数字都会满足大于nums[i] * 3，他们一共有list.size() - where个，所以

count += list.size() - where; 这一步做完后就算遍历了这个数字了，再用一次二分法

找到它在list中第一个比它大的数的下标where，插入到list的where下标位置即可

代码

import java.util.*;

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

    public int find(List<Integer> list,Integer num){
        Integer left = 0;
        //这里一定要注意right = list.size()，这样在list里面找不到合适的数的时候
        //查询的结果会为数组最后一个元素的下标 + 1
        //这样才不会有问题，否则返回数组最后一个元素，但数组最后一个元素是不满足要求的
        Integer right = list.size();
        Integer mid = 0;
        while(left < right){
            mid = left + (right - left) / 2;
            if(list.get(mid)>num){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return left;
    }
}

复杂度分析

时间复杂度：$o(n logn n)$

分析：因为我在list中准确的插入新遍历过的元素还需要n时间

空间复杂度：$o(n)$

分析：因为维护了一个辅助list

[ninghuang456]

class Solution {

    public int solve(int[] nums) {
        int res = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i ++){
            int index = searchInsert(nums, nums[i] * 3);
          res += nums.length - index;
        }
        return res;
    }

     public int searchInsert(int[] nums, int target) {
        int left = 0; int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
// Time Nlog(N), Space O(1);

[haixiaolu]

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

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

            left_i, right_j = start, mid + 1
            while left_i <= mid and right_j <= end:
                if nums[left_i] <= 3 * nums[right_j]:
                    left_i += 1
                else:
                    self.count += mid - left_i + 1
                    right_j += 1

            while left <= mid:
                temp.append(nums[left])
                left += 1
            while right <= mid:
                temp.append(nums[right])
                right += 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) // 2
            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.count 

[bubblefu]

class Solution:
    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)

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

[Yachen-Guo]

思路

归并排序，分而治之。在归并排序的过程中计数。

代码

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

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

    private int merge(int[] nums, int left, int mid, int right){
        int lP = left;
        int rP = mid + 1;
        int res = 0;
        while(lP <= mid && rP <= right){
            if((long)nums[lP] > 3 * (long)nums[rP]){
                res += mid - lP + 1;
                rP++;
            } else{
                lP++;
            }
        }

        lP = left;
        rP = mid + 1;
        int sorted[] = new int[right - left + 1];
        int idx = 0;

        while(lP <= mid && rP <= right){
            if(nums[lP] <= nums[rP]){
                sorted[idx++] = nums[lP++];
            } else{
                sorted[idx++] = nums[rP++];
            }
        } 

        while(lP <= mid){
            sorted[idx++] = nums[lP++];
        }

        while(rP <= right){
            sorted[idx++] = nums[rP++];
        }

        System.arraycopy(sorted,0,nums,left,right-left+1);

        return res;
    }
}

[LannyX]

思路

merge sort

代码

leetcode 493
class Solution {
    public int reversePairs(int[] nums) {
        if(nums.length < 2) return 0;
        return sort(nums, 0, nums.length - 1);
    }
    private int sort(int[] nums, int left, int right){
        if(left >= right) return 0;
        int mid = (right + left)/2;
        int leftRes = sort(nums, left, mid);
        int rightRes = sort(nums, mid + 1, right);

        return leftRes + rightRes + merge(nums, left, mid, right);
    }

    private int merge(int[] nums, int left, int mid, int right){
        int[] tmp = new int[right - left + 1];
        int i = left, j = mid + 1, res = 0, flag = 0;

        while(i <= mid && j <= right){
            if(nums[i] > 2 * (long)nums[j]){
                res += mid - i + 1;
                j++;
            }else{
                i++;
            }
        }
        i = left;
        j = mid + 1;
        while(i <= mid && j <= right){
            if(nums[i] < nums[j]){
                tmp[flag++] = nums[i++];
            }else{
                tmp[flag++] = nums[j++];
            }
        }
        while(i <= mid){
            tmp[flag++] = nums[i++];
        }
        while(j <= right){
            tmp[flag++] = nums[j++];
        }
        for(int k = 0; k < tmp.length; k++){
            nums[left+k] = tmp[k];
        }
        return res;
    }
}

复杂度分析

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

[hdyhdy]

思路： 二分法

func reversePairs(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }

    n1 := append([]int(nil),nums[:n/2]...)
    n2 := append([]int(nil),nums[n/2:]...)
    cnt := reversePairs(n1) + reversePairs(n2)

    j := 0 
    for _,v := range n1 {
        for j < len(n2) && v > 2 * n2[j] {
            j ++ 
        }
        cnt += j
    }

    p1,p2 := 0,0
    for i := range nums {
        if p1 < len(n1) && (p2 == len(n2) || n1[p1] <= n2[p2] ) {
            nums[i] = n1[p1]
            p1 ++
        }else {
            nums[i] = n2[p2]
            p2 ++ 
        }
    }
    return cnt
}

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

[cszys888]

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(nums, nums_sorted, l, r):
            if l == r:
                return 0
            mid = (l + r) // 2
            n1 = merge_sort(nums, nums_sorted, l, mid)
            n2 = merge_sort(nums, nums_sorted, mid + 1, r)
            n3 = 0
            j = mid + 1
            for i in range(l, mid+1):
                while j <= r and nums[i] > 3*nums[j]:
                    j += 1
                n3 += j - mid - 1
            ret = n1 + n2 + n3

            # merge sort
            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
                    k += 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 ret

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

time complexity: O(N*LogN) space complexity: O(N)

[watchpoints]

思路

排序之后，位置发生变化，

为什么归并排序，能统计逆序对呢

代码

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

[spacker-343]

思路

分治

代码

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

    private int mergeSort(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int l = mergeSort(nums, left, mid);
        int r = mergeSort(nums, mid + 1, right);
        int ret = l + r;
        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) {
            if ((long) nums[i] > 2 * (long) nums[j]) {
                ret += mid - i + 1;
                j++;
            } else {
                i++;
            }
        }
        // 统计完之后合并
        merge(nums, left, right, mid);
        return ret;
    }

    private void merge(int[] nums, int left, int right, int mid) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int idx = 0;
        while (i <= mid && j <= right) {
            if (nums[i] < nums[j]) {
                temp[idx++] = nums[i++];
            } else {
                temp[idx++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[idx++] = nums[i++];
        }
        while (j <= right) {
            temp[idx++] = nums[j++];
        }
        for (int k = left; k <= right; k++) {
            nums[k] = temp[k - left];
        }
    }
}

[Moin-Jer]

思路

---

二分

代码

---

import java.util.*;

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

    private int mergeSort(int[] nums, int l, int r, int[] tmp) {
        if (l >= r) {
            return 0;
        }
        int mid = (l + r) >>> 1;
        int ll = mergeSort(nums, l, mid, tmp);
        int rr = mergeSort(nums, mid + 1, r, tmp);
        int mm = merge(nums, l, mid, r, tmp);
        return ll + mm + rr;
    }

    private int merge(int[] nums, int l, int m, int r, int[] tmp) {
        int i = l, j = m + 1, k = 0;
        int res = 0;
        while (i <= m && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        while (i <= m) {
            tmp[k++] = nums[i++];
        }
        while (j <= r) {
            tmp[k++] = nums[j++];
        }

        i = l;
        j = m + 1;
        while (i <= m && j <= r) {
            if (nums[i] <= nums[j] * 3) {
                i++;
            } else {
                res += m - i + 1;
                ++j;
            }
        }

        k = 0;
        for (i = l; i <= r;) {
            nums[i++] = tmp[k++];
        }
        return res;
    }
}

复杂度分析

---

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

[iambigchen]

思路

归并排序，在排序过程中，统计翻转对的数量。start到mid、mid+1到end都是升序，如果nums[ti] > 2 nums[tj]的值，则从ti到mid的每个值都是符合nums[ti] > 2 nums[tj]的。 排序在找数之前和之后都不影响

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    let res = 0
    function merge(nums, start, mid, end) {
        let i = start
        let j = mid + 1
        let temp = []
        while(i <= mid && j <= end) {
            if (nums[i] <= nums[j]) {
                temp.push(nums[i])
                i++
            } else {
                temp.push(nums[j])
                j++
            }
        }
        let ti = start
        let tj = mid + 1
        while(ti <= mid && tj <= end) {
            if (nums[ti] <=  3 * nums[tj]) {
                ti++
            } else {
                res += mid - ti + 1
                tj++
            }
        }
        while(i <= mid) {
            temp.push(nums[i])
            i++
        }
        while(j <= end) {
            temp.push(nums[j])
            j++
        }
        for(let index = 0; index < temp.length; index++) {
            nums[start + index] = temp[index]
        }
    }
    function mergeSort(nums, start, end) {
        if (start >= end) return
        let mid = (start + end) >> 1
        mergeSort(nums, start, mid)
        mergeSort(nums, mid+1, end)
        merge(nums, start, mid, end)
    }
    mergeSort(nums, 0, nums.length-1)
    return res
};

复杂度分析

令 n 为数组长度。

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

[JudyZhou95]

思路

merge sort的过程中 找到左右两边reverse的pair

代码

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

            if i <= mid:
                temp += nums[i:mid+1]
            if j <= end:
                temp += nums[j: end+1]

            ci, cj = start, mid+1
            while ci <= mid and cj <= end:
                if nums[ci] <= 3*nums[cj]:
                    ci += 1
                else:
                    self.cnt += mid-ci+1
                    cj += 1

            nums[start:end+1] = temp

            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

复杂度

TC: O(NlogN) SC: O(N)

[charlestang]

思路

分治法

通过分治法，将数组切割成两份，并分别排序，返回两半数组内部满足条件的逆序对数。然后左侧和右侧分别搜索一个数字，满足题目要求的条件，然后统计逆序对数量。

排序算法返回逆序对总数。

代码

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        # 归并排序，返回逆序对的数量
        def mergeSort(left: int, right: int) -> int:
            if left == right: return 0
            mid = (left + right) // 2
            retL = mergeSort(left, mid)
            retR = mergeSort(mid + 1, right)
            ret = retL + retR

            i = left
            j = mid + 1

            while i <= mid:
                while j <= right and nums[i] > 3 * nums[j]:
                    j += 1
                ret += j - mid -1
                i += 1

            # 合并
            temp = []
            i, j = left, mid + 1
            while i <= mid or j <= right:
                if i <= mid and j <= right and nums[i] <= nums[j]:
                    temp.append(nums[i])
                    i += 1
                elif i <= mid and j <= right and nums[i] > nums[j]:
                    temp.append(nums[j])
                    j += 1
                else:
                    if i <= mid:
                        temp.append(nums[i])
                        i += 1
                    else:
                        temp.append(nums[j])
                        j += 1
            st = left
            for n in temp:
                nums[st] = n
                st += 1
            return ret
        ret = mergeSort(0, len(nums) - 1)
        return ret

时间复杂度 O(nlogn) 空间复杂度 排序过程中利用到临时数组，所以 O(n)

[1149004121]

Triple Inversion

思路

二分法搜索，用一个临时数组保存已访问过的数的有序排序，遍历下标从0到n - 1的数，在临时数组中找到第一个大于三倍它的下标，计数增加，最后将该数插入到临时数组中。

代码

class Solution {
    solve(nums) {
        let res = 0;
        const n = nums.length;
        let sorted = [];
        for(let i = 0; i < n; i++){
            let left_border = this.findLeftBorder(sorted, 3 * nums[i]);
            res += i - left_border;
            let index = this.findLeftBorder(sorted, nums[i]);
            sorted.splice(index, 0, nums[i]);
        };
        return res;
    };
    findLeftBorder(arr, value){
        let left = 0, right = arr.length;
        while(left < right){
            let mid = (left + right) >> 1;
            if(arr[mid] > value) right = mid;
            else left = mid + 1;
        };
        return left;       
    };
}

复杂度分析

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

[zhangzz2015]

思路

• 利用Merge sort方法，在sort过程能保持左右两部分有序，同时左边的index，小于右边的index。当进行merge 两部分的有序vector，可同时找到有有多少满足条件的目标对。时间复杂度为O(nlognlogn)，空间复杂度为O(n)。

关键点

代码

• 语言支持：C++

C++ Code:

int upperbound(vector<int>& nums, int left, int right, int target)
{
     while(left<=right)
     {
         int middle = left + (right - left)/2; 

         if(nums[middle]>target)
         {
              right = middle-1; 
         }
         else
         {
             left = middle+1; 
         }
     }
    //  [right left]
    return left;      

}

void  mergeTwoPart(vector<int>& nums, int left, int middle, int right,  int& ret)
{ 
      int left1 = left ; 
      int right1 = middle; 
      int left2 = middle+1; 
      int right2 = right; 
      vector<int> tmp(right - left+1);
      int count =0; 
      while(left1 <=right1 && left2 <=right2)
      {
           if(nums[left1] <=nums[left2] ) 
           {
               tmp[count] = nums[left1]; 
               count++; 
               left1++; 
           }
           else
           {
               int large_index = upperbound(nums, left1, right1, nums[left2]*3 );
               if(large_index<=right1)
                  ret +=(right1 - large_index+1); 
                //  [left1   right1][left2  right2]; 
                 //  [left1+1]                  
                 tmp[count] = nums[left2]; 
                 count++; 
                 left2++;                   
           }
      }
     while(left1<=right1)
     {
         tmp[count] = nums[left1]; 
         left1++; 
         count++;
     }
     while(left2<=right2)
     {
         tmp[count] = nums[left2]; 
         left2++;
         count++;  
     }
     for(int i=left; i <= right; i++)
     {
         nums[i] = tmp[i-left]; 
     }      
}

void MergeSort(vector<int>& nums, int left, int right, int& ret)
{
     if(left>=right)
         return ; 
      int middle = left + (right - left)/2; 

      MergeSort(nums, left, middle, ret); 
      MergeSort(nums, middle+1, right,  ret); 
      mergeTwoPart(nums, left, middle, right, ret);    
}

int solve(vector<int>& nums) {
    int ret=0;
    MergeSort(nums, 0, nums.size()-1, ret); 
    return ret; 

}

[Tiquiero]

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    let res = 0
    function merge(nums, start, mid, end) {
        let i = start
        let j = mid + 1
        let temp = []
        while(i <= mid && j <= end) {
            if (nums[i] <= nums[j]) {
                temp.push(nums[i])
                i++
            } else {
                temp.push(nums[j])
                j++
            }
        }
        let ti = start
        let tj = mid + 1
        while(ti <= mid && tj <= end) {
            if (nums[ti] <=  3 * nums[tj]) {
                ti++
            } else {
                res += mid - ti + 1
                tj++
            }
        }
        while(i <= mid) {
            temp.push(nums[i])
            i++
        }
        while(j <= end) {
            temp.push(nums[j])
            j++
        }
        for(let index = 0; index < temp.length; index++) {
            nums[start + index] = temp[index]
        }
    }
    function mergeSort(nums, start, end) {
        if (start >= end) return
        let mid = (start + end) >> 1
        mergeSort(nums, start, mid)
        mergeSort(nums, mid+1, end)
        merge(nums, start, mid, end)
    }
    mergeSort(nums, 0, nums.length-1)
    return res
};

[falconruo]

思路

归并排序

复杂度

• 时间复杂度: O(NlogN), N为数组长度
• 空间复杂度: O(N)

代码(C++)

void mergesort(vector<int>& nums, vector<int>& tmp, int left, int right,int &res)
{
    if(left >= right) return;
    int mid = left + (right - left) / 2;
    mergesort(nums, tmp, left, mid, res);
    mergesort(nums, tmp, mid + 1, right,res);

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

    i = left;
    j = mid + 1;
    int t = 0;
    while(i <= mid && j <= right)
        if(nums[i] > nums[j])
            tmp[t++] = nums[j++];
        else
            tmp[t++] = nums[i++];
    while (i <= mid)
        tmp[t++] = nums[i++];

    while (j <= right)
        tmp[t++] = nums[j++];
    t = 0;
    while (left <= right)
        nums[left++] = tmp[t++];
}

int solve(vector<int>& nums) {
    int size = nums.size();
    int l = 0;
    int r = size-1;
    int res = 0;
    vector<int> tmp(size);
    mergesort(nums, tmp, l, r, res);
    return res;
}

[zol013]

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

[zhiyuanpeng]

class Solution:
    def solve(self, nums):
        sortlist = Sortedlist()
        cnt = 0
        for num in nums:
            cnt += len(sortlist) - sortlist.bisect_right(num * 3)
            sortlist.add(num)
        return cnt      

[KennethAlgol]

class Solution {

    public int solve(int[] nums) {
        int res = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i ++){
            int index = searchInsert(nums, nums[i] * 3);
          res += nums.length - index;
        }
        return res;
    }

     public int searchInsert(int[] nums, int target) {
        int left = 0; int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

复杂度分析

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

[GaoMinghao]

思路

二分的方法还是没看明白，明天再试试，不过分治的方法倒是看明白了，个人觉得num[i] > num[j] 和 num[i] > num[j]*3 在写法上还是有区别的，因为前者可以直接将计算过程融入归并排序的过程中，后者需要单独出来写

代码

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

    private int mergeSort(int[] nums, int left, int right) {
        if(left >= right)
            return 0;
        int[] temp = new int[right-left+1];
        int ans = 0;
        int mid = (left + right) / 2;
        int leftCount = mergeSort(nums, left, mid);
        int rightCount = mergeSort(nums, mid+1, right);
        // 左右分治完成之后，除了各得出左右的节点之外，左右两边的数组都是各自有序的
        // 统计下标对的数量
        int i = left, j = mid+1;
        while(i <= mid) {
            while (j <= right && nums[i] > nums[j]*3) {
                j++;
            }
            ans += j-mid-1; // nums[j]已经不满足条件了 -> j-1 - (mid+1) + 1
            i++;
        }
        // 合并数据并排序
        int p = left, q = mid + 1, t = 0;
        while(p <= mid && q <= right) {
            if(nums[p] <= nums[q])
                temp[t++] = nums[p++];
            else
                temp[t++] = nums[q++];
        }
        while(p <= mid) temp[t++] = nums[p++];
        while(q <= right) temp[t++]  = nums[q++];
        for(int a = 0, b = left; a < t; a++,b++ ) nums[b] = temp[a];
        return leftCount+rightCount+ans;
    }
}

复杂度

时间复杂度O(NlgN) 空间复杂度O(N)

[ywang525]

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

    for n in nums:            
        index = self.find_index_in_sorted_list(sorted_list,n * 3)
        res += len(sorted_list) - index

    return res

def find_index_in_sorted_list(self, sorted_list, n):

    left = 0
    right = len(sorted_list) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if n < sorted_list[mid]:
            right = mid - 1
        else:
            left = mid + 1

    return left

[callmeerika]

思路

利用归并排序

代码

 class Solution {
    mergeSort(nums, left, right) {
      if (left >= right) return 0;
      let mid = Math.floor((right + left) / 2);
      let res = this.mergeSort(nums, left, mid) + this.mergeSort(nums, mid + 1, right);
      let p = left;
      let q = mid + 1;
      while (p <= mid) {
        while (q <= right && nums[p] > 3 * nums[q]) {
          q++;
        }
        res += q - mid - 1;
        p++;
      }
      let i = left;
      let j = mid + 1;
      let k = 0;
      let arr = new Array(right - left + 1);
      while (i <= mid && j <= right) {
        if (nums[i] < nums[j]) {
          arr[k++] = nums[i++];
        } else {
          arr[k++] = nums[j++];
        }
      }
      while (i <= mid) {
        arr[k++] = nums[i++];
      }
      while (j <= right) {
        arr[k++] = nums[j++];
      }
      for (let i = 0; i < arr.length; i++) {
        nums[left + i] = arr[i];
      }
      return res;
    }
    solve(nums) {
      if (nums.length === 0) return 0;
      return this.mergeSort(nums, 0, nums.length - 1);
    }
  }

复杂度

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

[biscuit279]

思路，归并排序的同事统计逆序数

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) // 2
            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)

[Myleswork]

思路

归并排序+二分查找

其实就是题目对应的hint

while merging two arrays in mergesort try to count the no of elements in second array whose thrice is smaller for each elements in first array.

代码

int res = 0;

int find(vector<int>& list, int l, int r,int target) {
    while (l <= r) {
        int mid = (r - l) / 2 + l;
        if (list[mid] <= target) r = mid-1;
        else l = mid+1;
    }
    return r + 1;
}

int merge(vector<int>& list,int l, int r, int m) {
    int i = l, j = m + 1, k = 0;
    int count = 0;
    vector<int> temp(r - l + 1);
    for (int left = r; left >= j; left--) {
        int tmp = find(list, l, j-1, list[left]*3)-l;
        if (tmp == 0) break;
        count += tmp;
    }
    while (i <= m && j <= r) {
        temp[k++] = list[i] >= list[j] ? list[i++] : list[j++];
    }
    while (i <= m) temp[k++] = list[i++];
    while (j <= r) temp[k++] = list[j++];
    for (i = l, k = 0; i <= r; i++, k++) {
        list[i] = temp[k];
    }
    return count;
}

void mergesort(vector<int>& list, int l, int r,int& res) {
    if (l >= r) return;
    int mid = (r - l) / 2 + l;
    mergesort(list, l, mid, res);
    mergesort(list, mid + 1, r, res);
    res += merge(list, l, r, mid);
}

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

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(1)

[harperz24]

class SummaryRanges {
    TreeMap<Integer, Integer> intervals;

    public SummaryRanges() {
        intervals = new TreeMap<Integer, Integer>();
    }

    public void addNum(int val) {

        Map.Entry<Integer, Integer> interval1 = intervals.ceilingEntry(val + 1);
        Map.Entry<Integer, Integer> interval0 = intervals.floorEntry(val);

        if (interval0 != null && interval0.getKey() <= val && val <= interval0.getValue()) return;    

        boolean leftAside = interval0 != null && interval0.getValue() + 1 == val;
        boolean rightAside = interval1 != null && interval1.getKey() - 1 == val;

        if (leftAside && rightAside) {

            int left = interval0.getKey(), right = interval1.getValue();
            intervals.remove(interval0.getKey());
            intervals.remove(interval1.getKey());
            intervals.put(left, right);

        } else if (leftAside) {
            intervals.put(interval0.getKey(), interval0.getValue() + 1);

        } else if (rightAside) {
            int right = interval1.getValue();
            intervals.remove(interval1.getKey());
            intervals.put(val, right);

        } else {
            intervals.put(val, val);
        }
    }

    public int[][] getIntervals() {
        int size = intervals.size();
        int[][] ans = new int[size][2];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : intervals.entrySet()) {
            int left = entry.getKey(), right = entry.getValue();
            ans[index][0] = left;
            ans[index][1] = right;
            ++index;
        }
        return ans;
    }
}