数据结构
网络
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 次浏览
广告