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

给定一个链表，我们需要找到链表中大于当前元素且出现在当前元素右侧的元素。需要将这些元素的计数替换到当前节点的值中。

让我们以包含以下字符的链表为例，并将每个节点替换为其超越者计数：

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

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

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

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

示例

以下是使用 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

解释

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

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

依此类推，对所有元素都适用

结论

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

更新于：2022 年 8 月 10 日

161 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告