資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學用 C++ 在無序陣列中找到 k 個最近的數字
假設我們有一個包含少數元素的陣列 A。這個陣列是無序的。我們還有其他兩個值 X 和 k。我們的任務是找出陣列 A 中距離 X 最近的 k 個數。如果元素 X 出現在陣列中，那麼它將不會顯示在輸出中。如果 A = [48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56]，X = 35，k = 4。結果將為 30、39、42、45。
為了解決這個問題，我們將使用堆資料結構。具體步驟如下 −
用前 k 個元素建立一個差的最大堆
對從第 k+1 個元素開始的每個元素重複以下步驟
找出當前元素到 x 的差
如果差大於堆的根，那麼忽略當前元素
否則，在移除根之後將當前元素插入堆中。
最終堆將有 k 個最接近的元素。
示例
#include <iostream>
#include<queue>
using namespace std;
void findKClosestNumbers(int arr[], int n, int x, int k) {
priority_queue<pair<int, int> > priorityQ;
for (int i = 0; i < k; i++)
priorityQ.push({ abs(arr[i] - x), i });
for (int i = k; i < n; i++) {
int diff = abs(arr[i] - x);
if (diff > priorityQ.top().first)
continue;
priorityQ.pop();
priorityQ.push({ diff, i });
}
while (priorityQ.empty() == false) {
cout << arr[priorityQ.top().second] << " ";
priorityQ.pop();
}
}
int main() {
int arr[] = {48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56};
int x = 35, k = 5;
int n = sizeof(arr) / sizeof(arr[0]);
findKClosestNumbers(arr, n, x, k);
}輸出
45 42 30 39 35
更新日期：2019-11-01
388 次瀏覽
廣告