資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中的巧合搜尋
假設我們有一個名為 nums 的唯一整數列表。我們必須找到使用標準二分查詢仍然可以成功找到的整數數量。
因此，如果輸入類似於 [2,6,4,3,10]，則輸出將為 3，因為如果我們使用二分查詢來查詢 4，則可以在第一次迭代中找到它。我們還可以在兩次迭代後找到 2 和 10。
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 help()，它將採用 target、一個數組和 nums，
low := 0
high := nums 的大小 - 1
當 low <= high 時，執行以下操作 -
mid := low + (high - low) / 2
如果 nums[mid] 與 target 相同，則 -
返回 true
如果 nums[mid] < target，則 -
low := mid + 1
否則
high := mid - 1
返回 false
從 main 方法執行以下操作 -
ret := 0
對於 nums 中的每個元素 i
ret := ret + help(i, nums)
返回 ret
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool help(int target, vector<int> & nums) {
int low = 0;
int high = nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return true;
if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
int solve(vector<int> & nums) {
int ret = 0;
for (int i : nums) {
ret += help(i, nums);
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = {2,6,4,3,10};
cout << (ob.solve(v));
}輸入
{2,6,4,3,10}輸出
3
更新於： 2020 年 9 月 2 日
185 次瀏覽
廣告