493.翻转对.py

#
# @lc app=leetcode.cn id=493 lang=python3
#
# [493] 翻转对
#
# https://leetcode.cn/problems/reverse-pairs/description/
#
# algorithms
# Hard (35.35%)
# Likes:    354
# Dislikes: 0
# Total Accepted:    31.1K
# Total Submissions: 87.8K
# Testcase Example:  '[1,3,2,3,1]'
#
# 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
# 
# 你需要返回给定数组中的重要翻转对的数量。
# 
# 示例 1:
# 
# 
# 输入: [1,3,2,3,1]
# 输出: 2
# 
# 
# 示例 2:
# 
# 
# 输入: [2,4,3,5,1]
# 输出: 3
# 
# 
# 注意:
# 
# 
# 给定数组的长度不会超过50000。
# 输入数组中的所有数字都在32位整数的表示范围内。
# 
# 
#

# @lc code=start
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        nums.reverse()
        max_num =max(nums)
        min_num =min(nums)
        data =  [0 for i in range(min_num,max_num+1)]
        count = 0
        for i in nums:
            if i>=0:
                count +=sum(data[:(i-min_num)>>1])
            else:
                count +=sum(data[:(i-min_num+1)])
            data[i-min_num] +=1

        return count

# @lc code=end