資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用 C++ 查詢最接近的 K 個元素
假設我們有一個排序陣列，還給定兩個整數 k 和 x，我們必須在該陣列中找到 k 個最接近 x 的元素。結果應按升序排序。如果存在平局，則始終優先考慮較小的元素。因此，如果輸入類似於 [1,2,3,4,5]，並且 k = 4，x = 3，則輸出將是 [1,2,3,4]
為了解決這個問題，我們將按照以下步驟進行 -
- 建立一個稱為 ans 的陣列
- 將 low 設定為 0，將 high 設定為陣列大小 - k
- 當 low < high
- mid := low + (high - low) /2
- 如果 x - arr[mid] > arr[mid + k] - x，則 low := mid + 1，否則 high := mid
- 對於 low 到 low + k 範圍內的每個 i
- 將 arr[i] 插入 ans 陣列
- 返回 ans
示例（C++）
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector <int> ans;
int low = 0;
int high = arr.size() - k;
while(low < high){
int mid = low + (high - low)/2;
if(x - arr[mid] > arr[mid + k] - x){
low = mid + 1;
}
else high = mid;
}
for(int i = low ; i < low + k ; i++)ans.push_back(arr[i]);
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5};
print_vector(ob.findClosestElements(v, 4, 3));
}輸入
[1,2,3,4,5] 4 3
輸出
[1,2,3,4]
更新於：29-4-2020
371 次瀏覽
廣告