【Day 39 】2024-05-16 - 493. 翻转对

[azl397985856]

493. 翻转对

入选理由

暂无

题目地址

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

前置知识

• 二分法

  题目描述

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

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

示例 1:

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

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

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

[Hermione666]

from typing import List import bisect

class Solution: def reversePairs(self, nums: List[int]) -> int: sorted_list = [] reverse_pairs_count = 0

    for num in reversed(nums):

        reverse_pairs_count += bisect.bisect_left(sorted_list, num)

        bisect.insort(sorted_list, 2 * num)

    return reverse_pairs_count

[zhiyuanpeng]

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

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

[xil324]

class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        if len(nums) > 1:
            mid = (len(nums)) // 2
            left = nums[:mid]
            right = nums[mid:]
            count += self.reversePairs(left)
            count += self.reversePairs(right)
            i = 0
            j = 0
            for i in range(len(left)):
                while j < len(right) and left[i] > right[j] * 2:
                    j += 1
                count += j
            i = j = k = 0
            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    nums[k] = left[i]
                    k+=1
                    i +=1
                else:
                    nums[k] = right[j]
                    j += 1
                    k += 1
            while i < len(left):
                nums[k] = left[i]
                k += 1
                i += 1
            while j < len(right):
                nums[k] = right[j]
                j += 1
                k += 1
        return count

[Dtjk]

class Solution: def reversePairs(self, nums: List[int]) -> int: tb, res = [], 0 for n in nums[::-1] : res += bisect.bisect_left(tb, n) n2 = 2*n idx = bisect.bisect_left(tb, n2) tb.insert(idx, n2) return res