資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢排序連結串列的中位數
在這個問題中，我們給定一個包含 N 個元素的排序連結串列。我們的任務是查詢排序連結串列的中位數。
排序連結串列是一個簡單的連結串列，其中所有元素都按特定順序排序。示例 - 4 -> 6 -> 7 -> 9 -> NULL
中位數是連結串列的中間元素。如果 N 是奇數，則可以將其找到為：中位數是第 (n/2)th 個元素
如果 N 是偶數 - 中位數是第 (n/2)th 個元素和第 (n/2 + 1)th 個元素的平均值。
讓我們舉個例子來理解這個問題，
Input: 2 -> 3 -> 4 -> 6 -> 9 -> NULL Output: 4
解決方案方法
解決此問題的一個簡單方法是透過遍歷連結串列來計算所有元素。
現在，如果計數為奇數，我們將再次遍歷連結串列，直到連結串列的第 N/2 個元素。
如果計數為偶數，我們將遍歷到第 N/2 個元素和第 N/2 + 1 個元素，將它們加起來再除以 2。
替代方法
解決此問題的另一種方法是使用雙指標遍歷連結串列並找到連結串列中元素的計數。
以下是如何在不計算元素數量的情況下查詢中位數的演算法。有兩個指標 pointer1 和 pointer2，根據條件，我們可以有：
如果 pointer1 不為空，則 pointer2 是中位數。
如果 pointer1 為空，則 (pointer2 節點的上一個節點 + pointer2 -> data)/2。
示例
程式說明我們解決方案的工作原理
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void findMedianValue(Node* head){
Node* ptr1 = head;
Node* ptr2 = head;
Node* prev = head;
if (head != NULL) {
while (ptr2 != NULL && ptr2->next != NULL) {
ptr2 = ptr2->next->next;
prev = ptr1;
ptr1 = ptr1->next;
}
if (ptr2 != NULL)
cout<<ptr1->data;
else
cout<<float(ptr1->data + prev->data) / 2;
}
}
void pushVal(struct Node** head_ref, int new_data){
Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main(){
struct Node* head = NULL;
pushVal(&head, 3);
pushVal(&head, 5);
pushVal(&head, 6);
pushVal(&head, 8);
pushVal(&head, 9);
pushVal(&head, 11);
cout<<"The median of the linked list is ";
findMedianValue(head);
return 0;
}輸出
The median of the linked list is 7
更新於: 2022年2月1日
384 次檢視
廣告