資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用 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 次瀏覽
廣告