Count the number of "reverse pairs" in an array

This article aims to record the algorithm problem of finding the inverse logarithm, but it involves another Leetcode algorithm problem of finding the inverse number, so the first part is the LeetCode [315] previously written, and the second part is the problem of finding the inverse pair number. (the second part is actually modified from the first part, and the principle is introduced in the first part)

1, LeetCode [315] calculates the number of elements on the right that are less than the current element (inverse ordinal number)

Title Description

Given an integer array nums, return a new array counts as required. The array counts has this property: the value of counts[i] is the number of elements less than num [i] on the right side of num [i].

Examples

Input: num = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
There are 2 smaller elements (2 and 1) on the right side of 5
There is only one smaller element (1) on the right side of 2
There is a smaller element (1) on the right side of 6
There are 0 smaller elements on the right side of 1

Algorithm idea

Merge and sort of divide and conquer

The important idea of this question is expanded by merging and sorting. First, add merging and sorting

#include<iostream>
#include<vector>
using namespace std;

// Combine two sorted arrays in order
void merge_sort_two_vec(vector<int>& sub_vec1, vector<int>& sub_vec2, vector<int>& vec) {
	int i = 0;
	int j = 0;
	while (i < sub_vec1.size() && j < sub_vec2.size())
	{
		if (sub_vec1[i] <= sub_vec2[j]) {
			vec.push_back(sub_vec1[i]);
			i++;
		}
		else
		{
			vec.push_back(sub_vec2[j]);
			j++;
		}
	}
	for (; i < sub_vec1.size(); i++)
	{
		vec.push_back(sub_vec1[i]);
	}
	for (; j < sub_vec2.size(); j++)
	{
		vec.push_back(sub_vec2[j]);
	}
}

// Merge sort
void merge_sort(vector<int>& vec) {
	
	// If there is only one number, it will be returned directly
	// That is, decompose the problem into enough hours in recursion
	if (vec.size() < 2) { 
		return;
	}
	int mid = vec.size() / 2;
	vector<int> sub_vec1;
	vector<int> sub_vec2;
	for (int i = 0; i < mid; i++)
	{
		sub_vec1.push_back(vec[i]);
	}
	for (int i = mid; i < vec.size(); i++) {
		sub_vec2.push_back(vec[i]);
	}
	merge_sort(sub_vec1);
	merge_sort(sub_vec2);
	vec.clear();
	merge_sort_two_vec(sub_vec1, sub_vec2, vec);
}

int main()
{
	int nums[] = { -3,9,4,10,23,5,11,-6,21,-7 };
	vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(nums[i]);
	}
	merge_sort(vec);
	for (int i = 0; i < 10; i++)
	{
		cout << vec[i] << " ";
	}
	return 0;
}

Algorithm idea

The picture is from the course of the elephant Academy

Each time there are two arrays that have been sorted, add a new array according to the algorithm of merging and sorting the first function (synthesizing the two sorted arrays in order) above, and the count in the first array is the value of J (i is the index of the first array and j is the index of the second array).

Algorithm code

class Solution {
public:
	vector<int> countSmaller(vector<int>& nums) {
		vector<pair<int, int>> vec;
		vector<int> count;
		for (int i = 0; i < nums.size(); i++)
		{
			vec.push_back(make_pair(nums[i], i));
			count.push_back(0); // Bind nums[i] and I as pair
		}
		merge_sort(vec, count);
		return count;
	}
private:
	void merge_sort_two_vec(
		vector<pair<int, int>>& sub_vec1,
		vector<pair<int, int>>& sub_vec2,
		vector<pair<int, int>>& vec,
		vector<int>& count
	) {
		int i = 0;
		int j = 0;
		while (i < sub_vec1.size() && j < sub_vec2.size())
		{
			if (sub_vec1[i].first <= sub_vec2[j].first) { // Compare the first element of pair
				count[sub_vec1[i].second] += j; // The second element epitome is used to record count
				vec.push_back(sub_vec1[i]);
				i++;
			}
			else
			{
				vec.push_back(sub_vec2[j]);
				j++;
			}
		}
		for (; i < sub_vec1.size(); i++)
		{
			count[sub_vec1[i].second] += j;
			vec.push_back(sub_vec1[i]);
		}
		for (; j < sub_vec2.size(); j++)
		{
			vec.push_back(sub_vec2[j]);
		}

	}
	void merge_sort(vector<pair<int, int>>& vec, vector<int>& count) {
		// If there is only one number, it will be returned directly
		// That is, decompose the problem into enough hours in recursion
		if (vec.size() < 2) {
			return;
		}
		int mid = vec.size() / 2;
		vector<pair<int, int>> sub_vec1;
		vector<pair<int, int>> sub_vec2;
		for (int i = 0; i < mid; i++)
		{
			sub_vec1.push_back(vec[i]);
		}
		for (int i = mid; i < vec.size(); i++) {
			sub_vec2.push_back(vec[i]);
		}
		merge_sort(sub_vec1,count);
		merge_sort(sub_vec2, count);
		vec.clear();
		merge_sort_two_vec(sub_vec1, sub_vec2, vec, count);

	}
};

ps: little elephant academy course https://www.bilibili.com/video/BV1GW411Q77S?t=7029&p=2

2, Find the number of pairs in reverse order

Count the number of "reverse pairs" in an array

Given an array, use divide and conquer to count the number of reverse pairs in the array.

Reverse order pair means that the value of the element with the smaller sequence number in the array is greater than the value of the element with the larger sequence number

For example, enter 3 5 2 4 6
Output 3
Because 3 and 2 constitute a reverse order pair; 5 and 2 constitute a reverse order pair; 5 and 4 form a reverse order pair
So there are three in total.

Divide and conquer algorithm

Based on the merge sorting algorithm,
In the ordinary merge sort, two functions are designed. The first is to merge two ordered arrays in order; The second is to sort the entire array. The general operation is to divide an array into two parts, then sort the two parts, and then merge the two arrays in order, which is the recursive algorithm of divide and conquer.

The algorithm for finding the number of pairs in reverse order is as follows:

  1. In the ordinary merge sort algorithm, when merging two ordered arrays (vec1, vec2), we set two index values i and j, i index the first array and j index the second array, and define a count record number in reverse order;
  2. In our merged array function, one operation is to put the small numbers in vec1[i] and vec2[j] into a new merged final array. At this time, if vec1[i] < = vec2[j], the next step is to add the elements of VEC to the new merged array. At this time, the index j is the number of numbers smaller than vec1[i] but behind it, that is, the number of pairs in reverse order, which we want to accumulate to count, After merging, you can get the total count of pairs in reverse order.

code:

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
	int reversePairs(vector<int>& nums) {
		int count = 0;
		merge_sort(nums, count);
		return count;
	}
private:
	// Orderly merge two ordered arrays
	void merge_sort_two_vec(
		vector<int>& sub_vec1,
		vector<int>& sub_vec2,
		vector<int>& vec,
		int& count
	) {
		int i = 0;
		int j = 0;
		while (i < sub_vec1.size() && j < sub_vec2.size())
		{
			if (sub_vec1[i] <= sub_vec2[j]) {
				count += j; // Put sub every time_ Vec1 [i] record count
				vec.push_back(sub_vec1[i]);
				i++;
			}
			else
			{
				vec.push_back(sub_vec2[j]);
				j++;
			}
		}
		for (; i < sub_vec1.size(); i++)
		{
			count += j;
			vec.push_back(sub_vec1[i]);
		}
		for (; j < sub_vec2.size(); j++)
		{
			vec.push_back(sub_vec2[j]);
		}

	}
	void merge_sort(vector<int>& vec, int& count) {
		// If there is only one number, it will be returned directly
		// That is, decompose the problem into enough hours in recursion
		if (vec.size() < 2) {
			return;
		}
		int mid = vec.size() / 2;
		vector<int> sub_vec1;
		vector<int> sub_vec2;
		for (int i = 0; i < mid; i++)
		{
			sub_vec1.push_back(vec[i]);
		}
		for (int i = mid; i < vec.size(); i++) {
			sub_vec2.push_back(vec[i]);
		}
		merge_sort(sub_vec1, count);
		merge_sort(sub_vec2, count);
		vec.clear();
		merge_sort_two_vec(sub_vec1, sub_vec2, vec, count);

	}
};
int main()
{
	Solution so;
	vector<int> nums;
	int temp;
	do
	{
		cin >> temp;
		nums.push_back(temp);
	} while (getchar() != '\n');
	cout << so.reversePairs(nums);
}

Tags: C++ Algorithm divide and conquer

Posted by nickiehow on Tue, 10 May 2022 23:36:25 +0300