• 注册
    • 查看作者
    • 领扣: 532题 逆序对

      532. Reverse Pairs

      Reverse pair is a pair of numbers (A[i], A[j]) such that A[i] > A[j] and i < j. Given an array, return the number of reverse pairs in the array.

      Example

      Example1

      Input:  A = [2, 4, 1, 3, 5]
      Output: 3
      Explanation:
      (2, 1), (4, 1), (4, 3) are reverse pairs

      Example2

      Input:  A = [1, 2, 3, 4]
      Output: 0
      Explanation:
      No reverse pair

      class Solution:

          """

          @param A: an array

          @return: total of reverse pairs

          """

          def reversePairs(self, A):
              if len(A) <= 1:
                  return 0 
              #pass by ref
              count = [0]
              
              def merge(A):
                  if len(A) <= 1:
                      return A 
                  
                  mid=len(A) //2
                  left =merge(A[:mid])
                  right =merge(A[mid:])
                  #iterate from 0 from 0:length of left
                  i = j = 0
                  
                  while i < len(left) and j < len(right):
                      if left[i] <= right[j]:
                          i += 1
                      else:
                          #add all apart from right, which that greater than right
                          count[0] += len(left) - i
                          j += 1
                  #use sorted for shortcut
                  return sorted(left+right)
           
                      
              merge (A)
              return count[0]

              

        Leetcode 上有一样的题目 有点不一样  需要是右边大两倍判定 所以修改

       if left[i] <= right[j] *2:

      即可.

      纽约州·法拉盛
    • 0
    • 1
    • 0
    • 503
    • 请登录之后再进行评论

      登录
    • 0
      管理员Lv. 44VIP小可爱
      打赏了100钻石。
    • 做任务