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 次浏览

启动你的 职业生涯

完成课程获得认证

开始
广告