Replace each node in a linked list with its surpasser count using C++

Given a linked list, we need to find an element in the given linked list that is greater than the right side of the current element. The count of these elements needs to be substituted into the value of the current node.

Let's take a linked list containing the following characters and replace each node with its surpasser count -

4 -> 6 -> 1 -> 4 -> 6 -> 8 -> 5 -> 8 -> 3

Start backward and traverse the linked list (so we don't need to worry about the current element on the left). Our data structure keeps track of the current element in sorted order. Replaces the current element in the sorted data structure with the total number of elements above it.

Through the recursive method, the linked list will be traversed backwards. Another option is PBDS. Using PBDS allows us to find elements that are strictly less than a certain key. We can add the current element and subtract it from the strictly smaller element.

PBDS does not allow duplicate elements. However, we need repeated elements to count. To make each entry unique, we will insert a pair in the PBDS (first = element, second = index). To find the total elements equal to the current element, we will use a hash map. A hash map stores the number of occurrences of each element (basic integer-to-integer mapping).

Example

The following is a C program to replace each node in a linked list with its transcendental number -

#include <iostream>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define oset tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

class Node {
   public:
   int value;
   Node * next;
   Node (int value) {
      this->value = value;
      next = NULL;
   }
};
void solve (Node * head, oset & os, unordered_map < int, int >&mp, int &count){
   if (head == NULL)
   return;
   solve (head->next, os, mp, count);
   count++;
   os.insert (
   {
      head->value, count}
   );
   mp[head->value]++;
   int numberOfElements = count - mp[head->value] - os.order_of_key ({ head->value, -1 });
   head->value = numberOfElements;
}
void printList (Node * head) {
   while (head) {
      cout << head->value << (head->next ? "->" : "");
      head = head->next;
   }
   cout << "\n";
}
int main () {
   Node * head = new Node (43);
   head->next = new Node (65);
   head->next->next = new Node (12);
   head->next->next->next = new Node (46);
   head->next->next->next->next = new Node (68);
   head->next->next->next->next->next = new Node (85);
   head->next->next->next->next->next->next = new Node (59);
   head->next->next->next->next->next->next->next = new Node (85);
   head->next->next->next->next->next->next->next->next = new Node (37);
   oset os;
   unordered_map < int, int >mp;
   int count = 0;
   printList (head);
   solve (head, os, mp, count);
   printList (head);
   return 0;
}

Output

43->65->12->46->68->85->59->85->30
6->3->6->4->2->0->1->0->0

illustrate

So, for the first element, element = [65, 46, 68, 85, 59, 85], which is 6

The second element, element = [68, 85, 85] i.e. 3

And so on for all elements

in conclusion

This question requires a certain understanding of data structure and recursion. We need to lay out methods and then, based on observations and knowledge, derive data structures that meet our needs. If you liked this article, read more and stay tuned.

The above is the detailed content of Replace each node in a linked list with its surpasser count using C++. For more information, please follow other related articles on the PHP Chinese website!