資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中連結串列中第一個不重複的元素
在這個問題中，我們給定一個大小為 N 的連結串列 LL。我們的任務是建立一個程式來查詢連結串列中不重複的元素。
連結串列是由資料結構組成的序列，這些資料結構透過連結連線在一起。
讓我們舉個例子來理解這個問題，
Input: LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5 Output: 1
說明 -
The elements with a single occurrence frequency are 1 and 6. Out of these 1 occurred first in the linked list.
解決方案方法
解決此問題的一種方法是建立一個雜湊表，該表將儲存元素及其出現的頻率。為了找到連結串列中第一個不重複的值，我們將遍歷連結串列並將雜湊對映中不存在的元素插入到雜湊對映中，初始出現頻率為 1。如果雜湊對映中存在任何元素，則增加其出現頻率。遍歷連結串列後，我們將檢查雜湊對映中出現頻率為 1 的值，並返回遇到的第一個值。
示例
程式說明我們解決方案的工作原理
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int findFirstNonRepLL(struct Node *head){
unordered_map<int, int> freqMap;
for (Node *temp=head; temp!=NULL; temp=temp->next){
freqMap[temp->data]++;
}
for (Node *temp=head; temp!=NULL; temp=temp->next){
if (freqMap[temp->data] == 1){
return temp->data;
}
}
return -1;
}
int main(){
struct Node* head = NULL;
push(&head, 5);
push(&head, 6);
push(&head, 2);
push(&head, 1);
push(&head, 4);
push(&head, 2);
push(&head, 6);
push(&head, 4);
cout<<"The first non repeating element of the linked list is "<<findFirstNonRepLL(head);
return 0;
}輸出
The first non repeating element of the linked list is 1
更新時間： 2022-02-01
170 次瀏覽
廣告