使用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

所有元素依此類推

結論

此題需要對資料結構和遞迴有一定的了解。我們需要列出方法，然後根據觀察和知識，推導出滿足我們需求的資料結構。如果您喜歡這篇文章，請閱讀更多內容並敬請關注。

以上是使用C++將鍊錶中的每個節點替換為其超越者計數的詳細內容。更多資訊請關注PHP中文網其他相關文章！