Giả sử chúng ta có một danh sách các số nguyên duy nhất được gọi là nums. Chúng tôi phải tìm số lượng số nguyên vẫn có thể được tìm thấy thành công bằng cách sử dụng tìm kiếm nhị phân tiêu chuẩn.
Vì vậy, nếu đầu vào là [2,6,4,3,10], thì đầu ra sẽ là 3, như nếu chúng ta sử dụng tìm kiếm nhị phân để tìm 4, lúc đầu chúng ta có thể tìm thấy nó sự lặp lại. Chúng tôi cũng có thể tìm thấy 2 và 10 sau hai lần lặp.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm help (), hàm này sẽ lấy đích, một mảng &nums,
-
thấp:=0
-
cao:=kích thước của nums - 1
-
trong khi thấp <=cao, làm -
-
giữa:=low + (cao - thấp) / 2
-
nếu nums [mid] giống với target, thì -
-
trả về true
-
-
nếu nums [mid]
-
thấp:=mid + 1
-
-
Nếu không
-
cao:=mid - 1
-
-
-
trả về false
-
Từ phương thức chính, thực hiện như sau -
-
ret:=0
-
cho mỗi phần tử tôi trong nums
-
ret:=ret + help (i, nums)
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{2,6,4,3,10} Đầu ra
3