Welcome to Subscribe On Youtube

493. Reverse Pairs

Description

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

 

Example 1:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2:

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

 

Constraints:

• 1 <= nums.length <= 5 * 104
• -231 <= nums[i] <= 231 - 1

Solutions

Solution 1

Merge Sort or Binary Indexed Tree or Segment Tree.

Solution 2

Fenwick tree, also called “Binary Indexed Tree” or Fenwick tree. It can efficiently implement the following two operations:

1. Single point update update(x, delta): Add a value delta to the number at position x in the sequence;
2. Prefix sum query query(x): Query the interval sum of the sequence [1,...x] interval, that is, the prefix sum of position x.

The time complexity of both operations is $O(\log n)$.

The most basic function of a Fenwick tree is to find the number of points smaller than a certain point x (the comparison here is an abstract concept, which can be the size of the number, the size of the coordinates, the size of the mass, etc.).

For example, given the array a[5] = {2, 5, 3, 4, 1}, find b[i] = 位置 i 左边小于等于 a[i] 的数的个数. For this example, b[5] = {0, 1, 1, 2, 0}.

The solution is to traverse the array directly, find query(a[i]) at each position, and then modify the Fenwick tree update(a[i], 1). When the range of numbers is relatively large, discretization is required, that is, deduplication and sorting are first performed, and then each number is numbered.

Solution 3

The line segment tree divides the entire interval into multiple discontinuous sub-intervals, and the number of sub-intervals does not exceed log(width). To update the value of an element, you only need to update log(width) intervals, and these intervals are all included in a large interval containing the element.

• Each node of the line segment tree represents an interval;
• The line segment tree has a unique root node, and the interval represented is the entire statistical range, such as [1, N];
• Each leaf node of the line segment tree represents a meta-interval [x, x] of length 1;
• For each internal node [l, r], its left son is [l, mid] and its right son is [mid + 1, r], where mid = ⌊(l + r) / 2⌋ (that is, rounded down).

• Java
• C++
• Python
• Go

• class Solution {
      public int reversePairs(int[] nums) {
          TreeSet<Long> ts = new TreeSet<>();
          for (int num : nums) {
              ts.add((long) num);
              ts.add((long) num * 2);
          }
          Map<Long, Integer> m = new HashMap<>();
          int idx = 0;
          for (long num : ts) {
              m.put(num, ++idx);
          }
          BinaryIndexedTree tree = new BinaryIndexedTree(m.size());
          int ans = 0;
          for (int i = nums.length - 1; i >= 0; --i) {
              int x = m.get((long) nums[i]);
              ans += tree.query(x - 1);
              tree.update(m.get((long) nums[i] * 2), 1);
          }
          return ans;
      }
  }
  
  class BinaryIndexedTree {
      private int n;
      private int[] c;
  
      public BinaryIndexedTree(int n) {
          this.n = n;
          c = new int[n + 1];
      }
  
      public void update(int x, int delta) {
          while (x <= n) {
              c[x] += delta;
              x += lowbit(x);
          }
      }
  
      public int query(int x) {
          int s = 0;
          while (x > 0) {
              s += c[x];
              x -= lowbit(x);
          }
          return s;
      }
  
      public static int lowbit(int x) {
          return x & -x;
      }
  }
  
  
  // Solution 2
  class Solution {
      public int reversePairs(int[] nums) {
          TreeSet<Long> ts = new TreeSet<>();
          for (int num : nums) {
              ts.add((long) num);
              ts.add((long) num * 2);
          }
          Map<Long, Integer> m = new HashMap<>();
          int idx = 0;
          for (long num : ts) {
              m.put(num, ++idx);
          }
          BinaryIndexedTree tree = new BinaryIndexedTree(m.size());
          int ans = 0;
          for (int i = nums.length - 1; i >= 0; --i) {
              int x = m.get((long) nums[i]);
              ans += tree.query(x - 1);
              tree.update(m.get((long) nums[i] * 2), 1);
          }
          return ans;
      }
  }
  
  class BinaryIndexedTree {
      private int n;
      private int[] c;
  
      public BinaryIndexedTree(int n) {
          this.n = n;
          c = new int[n + 1];
      }
  
      public void update(int x, int delta) {
          while (x <= n) {
              c[x] += delta;
              x += lowbit(x);
          }
      }
  
      public int query(int x) {
          int s = 0;
          while (x > 0) {
              s += c[x];
              x -= lowbit(x);
          }
          return s;
      }
  
      public static int lowbit(int x) {
          return x & -x;
      }
  }
  
  
  
  // Solution 3
  class Solution {
      public int reversePairs(int[] nums) {
          TreeSet<Long> ts = new TreeSet<>();
          for (int num : nums) {
              ts.add((long) num);
              ts.add((long) num * 2);
          }
          Map<Long, Integer> m = new HashMap<>();
          int idx = 0;
          for (long num : ts) {
              m.put(num, ++idx);
          }
          SegmentTree tree = new SegmentTree(m.size());
          int ans = 0;
          for (int i = nums.length - 1; i >= 0; --i) {
              int x = m.get((long) nums[i]);
              ans += tree.query(1, 1, x - 1);
              tree.modify(1, m.get((long) nums[i] * 2), 1);
          }
          return ans;
      }
  }
  
  class Node {
      int l;
      int r;
      int v;
  }
  
  class SegmentTree {
      private Node[] tr;
  
      public SegmentTree(int n) {
          tr = new Node[4 * n];
          for (int i = 0; i < tr.length; ++i) {
              tr[i] = new Node();
          }
          build(1, 1, n);
      }
  
      public void build(int u, int l, int r) {
          tr[u].l = l;
          tr[u].r = r;
          if (l == r) {
              return;
          }
          int mid = (l + r) >> 1;
          build(u << 1, l, mid);
          build(u << 1 | 1, mid + 1, r);
      }
  
      public void modify(int u, int x, int v) {
          if (tr[u].l == x && tr[u].r == x) {
              tr[u].v += v;
              return;
          }
          int mid = (tr[u].l + tr[u].r) >> 1;
          if (x <= mid) {
              modify(u << 1, x, v);
          } else {
              modify(u << 1 | 1, x, v);
          }
          pushup(u);
      }
  
      public void pushup(int u) {
          tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
      }
  
      public int query(int u, int l, int r) {
          if (tr[u].l >= l && tr[u].r <= r) {
              return tr[u].v;
          }
          int mid = (tr[u].l + tr[u].r) >> 1;
          int v = 0;
          if (l <= mid) {
              v += query(u << 1, l, r);
          }
          if (r > mid) {
              v += query(u << 1 | 1, l, r);
          }
          return v;
      }
  }
  
  

• class BinaryIndexedTree {
  public:
      int n;
      vector<int> c;
  
      BinaryIndexedTree(int _n)
          : n(_n)
          , c(_n + 1) {}
  
      void update(int x, int delta) {
          while (x <= n) {
              c[x] += delta;
              x += lowbit(x);
          }
      }
  
      int query(int x) {
          int s = 0;
          while (x > 0) {
              s += c[x];
              x -= lowbit(x);
          }
          return s;
      }
  
      int lowbit(int x) {
          return x & -x;
      }
  };
  
  class Solution {
  public:
      int reversePairs(vector<int>& nums) {
          set<long long> s;
          for (int num : nums) {
              s.insert(num);
              s.insert(num * 2ll);
          }
          unordered_map<long long, int> m;
          int idx = 0;
          for (long long num : s) m[num] = ++idx;
          BinaryIndexedTree* tree = new BinaryIndexedTree(m.size());
          int ans = 0;
          for (int i = nums.size() - 1; i >= 0; --i) {
              ans += tree->query(m[nums[i]] - 1);
              tree->update(m[nums[i] * 2ll], 1);
          }
          return ans;
      }
  };
  
  
  // Solution 2
  class BinaryIndexedTree {
  public:
      int n;
      vector<int> c;
  
      BinaryIndexedTree(int _n)
          : n(_n)
          , c(_n + 1) {}
  
      void update(int x, int delta) {
          while (x <= n) {
              c[x] += delta;
              x += lowbit(x);
          }
      }
  
      int query(int x) {
          int s = 0;
          while (x > 0) {
              s += c[x];
              x -= lowbit(x);
          }
          return s;
      }
  
      int lowbit(int x) {
          return x & -x;
      }
  };
  
  class Solution {
  public:
      int reversePairs(vector<int>& nums) {
          set<long long> s;
          for (int num : nums) {
              s.insert(num);
              s.insert(num * 2ll);
          }
          unordered_map<long long, int> m;
          int idx = 0;
          for (long long num : s) m[num] = ++idx;
          BinaryIndexedTree* tree = new BinaryIndexedTree(m.size());
          int ans = 0;
          for (int i = nums.size() - 1; i >= 0; --i) {
              ans += tree->query(m[nums[i]] - 1);
              tree->update(m[nums[i] * 2ll], 1);
          }
          return ans;
      }
  };
  
  
  
  // Solution 3
  class Node {
  public:
      int l;
      int r;
      int v;
  };
  
  class SegmentTree {
  public:
      vector<Node*> tr;
  
      SegmentTree(int n) {
          tr.resize(4 * n);
          for (int i = 0; i < tr.size(); ++i) tr[i] = new Node();
          build(1, 1, n);
      }
  
      void build(int u, int l, int r) {
          tr[u]->l = l;
          tr[u]->r = r;
          if (l == r) return;
          int mid = (l + r) >> 1;
          build(u << 1, l, mid);
          build(u << 1 | 1, mid + 1, r);
      }
  
      void modify(int u, int x, int v) {
          if (tr[u]->l == x && tr[u]->r == x) {
              tr[u]->v += v;
              return;
          }
          int mid = (tr[u]->l + tr[u]->r) >> 1;
          if (x <= mid)
              modify(u << 1, x, v);
          else
              modify(u << 1 | 1, x, v);
          pushup(u);
      }
  
      void pushup(int u) {
          tr[u]->v = tr[u << 1]->v + tr[u << 1 | 1]->v;
      }
  
      int query(int u, int l, int r) {
          if (tr[u]->l >= l && tr[u]->r <= r) return tr[u]->v;
          int mid = (tr[u]->l + tr[u]->r) >> 1;
          int v = 0;
          if (l <= mid) v = query(u << 1, l, r);
          if (r > mid) v += query(u << 1 | 1, l, r);
          return v;
      }
  };
  
  class Solution {
  public:
      int reversePairs(vector<int>& nums) {
          set<long long> s;
          for (int num : nums) {
              s.insert(num);
              s.insert(num * 2ll);
          }
          unordered_map<long long, int> m;
          int idx = 0;
          for (long long num : s) m[num] = ++idx;
          SegmentTree* tree = new SegmentTree(m.size());
          int ans = 0;
          for (int i = nums.size() - 1; i >= 0; --i) {
              ans += tree->query(1, 1, m[nums[i]] - 1);
              tree->modify(1, m[nums[i] * 2ll], 1);
          }
          return ans;
      }
  };
  
  

• class BinaryIndexedTree:
      def __init__(self, n):
          self.n = n
          self.c = [0] * (n + 1)
  
      @staticmethod
      def lowbit(x):
          return x & -x
  
      def update(self, x, delta):
          while x <= self.n:
              self.c[x] += delta
              x += BinaryIndexedTree.lowbit(x)
  
      def query(self, x):
          s = 0
          while x > 0:
              s += self.c[x]
              x -= BinaryIndexedTree.lowbit(x)
          return s
  
  
  class Solution:
      def reversePairs(self, nums: List[int]) -> int:
          s = set()
          for num in nums:
              s.add(num)
              s.add(num * 2)
          alls = sorted(s)
          m = {v: i for i, v in enumerate(alls, 1)}
          ans = 0
          tree = BinaryIndexedTree(len(m))
          for num in nums[::-1]:
              ans += tree.query(m[num] - 1)
              tree.update(m[num * 2], 1)
          return ans
  
  
  # Solution 2
  class BinaryIndexedTree:
      def __init__(self, n):
          self.n = n
          self.c = [0] * (n + 1)
  
      @staticmethod
      def lowbit(x):
          return x & -x
  
      def update(self, x, delta):
          while x <= self.n:
              self.c[x] += delta
              x += BinaryIndexedTree.lowbit(x)
  
      def query(self, x):
          s = 0
          while x > 0:
              s += self.c[x]
              x -= BinaryIndexedTree.lowbit(x)
          return s
  
  
  class Solution:
      def reversePairs(self, nums: List[int]) -> int:
          s = set()
          for num in nums:
              s.add(num)
              s.add(num * 2)
          alls = sorted(s)
          m = {v: i for i, v in enumerate(alls, 1)}
          ans = 0
          tree = BinaryIndexedTree(len(m))
          for num in nums[::-1]:
              ans += tree.query(m[num] - 1)
              tree.update(m[num * 2], 1)
          return ans
  
  
  
  # Solution 3
  class Node:
      def __init__(self):
          self.l = 0
          self.r = 0
          self.v = 0
  
  
  class SegmentTree:
      def __init__(self, n):
          self.tr = [Node() for _ in range(4 * n)]
          self.build(1, 1, n)
  
      def build(self, u, l, r):
          self.tr[u].l = l
          self.tr[u].r = r
          if l == r:
              return
          mid = (l + r) >> 1
          self.build(u << 1, l, mid)
          self.build(u << 1 | 1, mid + 1, r)
  
      def modify(self, u, x, v):
          if self.tr[u].l == x and self.tr[u].r == x:
              self.tr[u].v += 1
              return
          mid = (self.tr[u].l + self.tr[u].r) >> 1
          if x <= mid:
              self.modify(u << 1, x, v)
          else:
              self.modify(u << 1 | 1, x, v)
          self.pushup(u)
  
      def pushup(self, u):
          self.tr[u].v = self.tr[u << 1].v + self.tr[u << 1 | 1].v
  
      def query(self, u, l, r):
          if self.tr[u].l >= l and self.tr[u].r <= r:
              return self.tr[u].v
          mid = (self.tr[u].l + self.tr[u].r) >> 1
          v = 0
          if l <= mid:
              v += self.query(u << 1, l, r)
          if r > mid:
              v += self.query(u << 1 | 1, l, r)
          return v
  
  
  class Solution:
      def reversePairs(self, nums: List[int]) -> int:
          s = set()
          for num in nums:
              s.add(num)
              s.add(num * 2)
          alls = sorted(s)
          m = {v: i for i, v in enumerate(alls, 1)}
          tree = SegmentTree(len(m))
          ans = 0
          for v in nums[::-1]:
              x = m[v]
              ans += tree.query(1, 1, x - 1)
              tree.modify(1, m[v * 2], 1)
          return ans
  
  

• type BinaryIndexedTree struct {
  	n int
  	c []int
  }
  
  func newBinaryIndexedTree(n int) *BinaryIndexedTree {
  	c := make([]int, n+1)
  	return &BinaryIndexedTree{n, c}
  }
  
  func (this *BinaryIndexedTree) lowbit(x int) int {
  	return x & -x
  }
  
  func (this *BinaryIndexedTree) update(x, delta int) {
  	for x <= this.n {
  		this.c[x] += delta
  		x += this.lowbit(x)
  	}
  }
  
  func (this *BinaryIndexedTree) query(x int) int {
  	s := 0
  	for x > 0 {
  		s += this.c[x]
  		x -= this.lowbit(x)
  	}
  	return s
  }
  
  func reversePairs(nums []int) int {
  	s := make(map[int]bool)
  	for _, num := range nums {
  		s[num] = true
  		s[num*2] = true
  	}
  	var alls []int
  	for num := range s {
  		alls = append(alls, num)
  	}
  	sort.Ints(alls)
  	m := make(map[int]int)
  	for i, num := range alls {
  		m[num] = i + 1
  	}
  	tree := newBinaryIndexedTree(len(m))
  	ans := 0
  	for i := len(nums) - 1; i >= 0; i-- {
  		ans += tree.query(m[nums[i]] - 1)
  		tree.update(m[nums[i]*2], 1)
  	}
  	return ans
  }
  
  
  // Solution 2
  type BinaryIndexedTree struct {
  	n int
  	c []int
  }
  
  func newBinaryIndexedTree(n int) *BinaryIndexedTree {
  	c := make([]int, n+1)
  	return &BinaryIndexedTree{n, c}
  }
  
  func (this *BinaryIndexedTree) lowbit(x int) int {
  	return x & -x
  }
  
  func (this *BinaryIndexedTree) update(x, delta int) {
  	for x <= this.n {
  		this.c[x] += delta
  		x += this.lowbit(x)
  	}
  }
  
  func (this *BinaryIndexedTree) query(x int) int {
  	s := 0
  	for x > 0 {
  		s += this.c[x]
  		x -= this.lowbit(x)
  	}
  	return s
  }
  
  func reversePairs(nums []int) int {
  	s := make(map[int]bool)
  	for _, num := range nums {
  		s[num] = true
  		s[num*2] = true
  	}
  	var alls []int
  	for num := range s {
  		alls = append(alls, num)
  	}
  	sort.Ints(alls)
  	m := make(map[int]int)
  	for i, num := range alls {
  		m[num] = i + 1
  	}
  	tree := newBinaryIndexedTree(len(m))
  	ans := 0
  	for i := len(nums) - 1; i >= 0; i-- {
  		ans += tree.query(m[nums[i]] - 1)
  		tree.update(m[nums[i]*2], 1)
  	}
  	return ans
  }
  
  

All Problems

All Solutions