資料結構
網路
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 = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56] 並且 X = 35，k = 4。輸出將為 30、39、42、45。
為了解決此問題，我們將採用二分搜尋方法。使用此方法，我們將獲得交叉點。如果找到交叉點的索引，我們可以在 O(k) 時間內列印最接近的 k 個元素。
示例
#include<iostream>
using namespace std;
int getCrossoverPoint(int arr[], int left, int right, int x) {
if (arr[right] <= x)
return right;
if (arr[left] > x)
return left;
int mid = (left + right)/2;
if(arr[mid] <= x && arr[mid+1] > x)
return mid;
if(arr[mid] < x)
return getCrossoverPoint(arr, mid+1, right, x);
return getCrossoverPoint(arr, left, mid - 1, x);
}
void findKClosestNumbers(int arr[], int x, int k, int n) {
int l = getCrossoverPoint(arr, 0, n-1, x);
int r = l+1;
int count = 0;
if (arr[l] == x) l--;
while (l >= 0 && r < n && count < k) {
if (x - arr[l] < arr[r] - x)
cout << arr[l--] << " ";
else
cout << arr[r++] << " ";
count++;
}
while (count < k && l >= 0){
cout << arr[l--] << " ";
count++;
}
while (count < k && r < n){
cout << arr[r++] << " ";
count++;
}
}
int main() {
int arr[] ={12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 35, k = 5;
findKClosestNumbers(arr, x, k, n);
}輸出
39 30 42 45 48
更新於：01-11-2019
107 瀏覽次數
廣告