使用C++将链表中的每个节点替换为其超越者计数

给定一个链表，我们需要在给定链表中查找大于当前元素右侧的元素。这些元素的计数需要代入当前节点的值。

让我们采用一个包含以下字符的链表，并用其超越者计数替换每个节点 –

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

从向后开始，遍历链表（因此我们不需要担心当前左边的元素）。我们的数据结构按排序顺序跟踪当前元素。将排序数据结构中的当前元素替换为其上方元素的总数。

立即学习“C++免费学习笔记（深入）”；

通过递归的方法，会向后遍历链表。另一种选择是 PBDS。使用 PBDS 可以让我们找到严格小于某个键的元素。我们可以添加当前元素并从严格较小的元素中减去它。

PBDS 不允许重复元素。然而，我们需要重复的元素来进行计数。为了使每个条目唯一，我们将在 PBDS 中插入一对（第一个 = 元素，第二个 = 索引）。为了找到等于当前元素的总元素，我们将使用哈希映射。哈希映射存储每个元素出现的次数（基本整数到整数映射）。

示例

以下是用其超越数替换链表中每个节点的 C++ 程序 –

#include #include #include #include #define oset tree, null_type,less>, 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 &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 value next ? "->" : "");      head = head->next;   }   cout 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 mp;   int count = 0;   printList (head);   solve (head, os, mp, count);   printList (head);   return 0;}

登录后复制

输出

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

登录后复制

说明

因此，对于第一个元素，element = [65, 46, 68, 85, 59, 85]，即 6

第二个元素，元素 = [68, 85, 85] 即 3

所有元素依此类推

结论

此题需要对数据结构和递归有一定的了解。我们需要列出方法，然后根据观察和知识，推导出满足我们需求的数据结构。如果您喜欢这篇文章，请阅读更多内容并敬请关注。

以上就是使用C++将链表中的每个节点替换为其超越者计数的详细内容，更多请关注【创想鸟】其它相关文章！