Maison > Article > développement back-end > Remplacez chaque nœud dans une liste chaînée par son nombre de dépassements en utilisant C++
给定一个链表,我们需要在给定链表中查找大于当前元素右侧的元素。这些元素的计数需要代入当前节点的值。
让我们采用一个包含以下字符的链表,并用其超越者计数替换每个节点 -
4 -> 6 -> 1 -> 4 -> 6 -> 8 -> 5 -> 8 -> 3
从向后开始,遍历链表(因此我们不需要担心当前左边的元素)。我们的数据结构按排序顺序跟踪当前元素。将排序数据结构中的当前元素替换为其上方元素的总数。
通过递归的方法,会向后遍历链表。另一种选择是 PBDS。使用 PBDS 可以让我们找到严格小于某个键的元素。我们可以添加当前元素并从严格较小的元素中减去它。
PBDS 不允许重复元素。然而,我们需要重复的元素来进行计数。为了使每个条目唯一,我们将在 PBDS 中插入一对(第一个 = 元素,第二个 = 索引)。为了找到等于当前元素的总元素,我们将使用哈希映射。哈希映射存储每个元素出现的次数(基本整数到整数映射)。
以下是用其超越数替换链表中每个节点的 C++ 程序 -
#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; }
43->65->12->46->68->85->59->85->30 6->3->6->4->2->0->1->0->0
因此,对于第一个元素,element = [65, 46, 68, 85, 59, 85],即 6
第二个元素,元素 = [68, 85, 85] 即 3
所有元素依此类推
此题需要对数据结构和递归有一定的了解。我们需要列出方法,然后根据观察和知识,推导出满足我们需求的数据结构。如果您喜欢这篇文章,请阅读更多内容并敬请关注。
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!