題目來源
- 來源平台：luogu 平台
- 題目編號：luogu-P2249
- 連結：題目連結
題目描述
給定一個長度為 n 的非負整數數列，該數列是單調不減的。然後有 m 次查詢，每次查詢給出一個整數 q，要求找出該數字在數列中第一次出現的編號（從 1 開始編號），如果沒有找到則輸出 -1。
思路與解法
分析
解法過程
方法一：暴力解法
- 介紹：對每次查詢，在數列中從頭開始遍歷，找到查詢數字的第一次出現位置。
- 優缺點：這種方法的實現非常簡單，但當數列和查詢數量都較大時，效率會很低。
方法二：二分搜索
- 介紹：由於數列是單調不減的，我們可以對每次查詢使用
lower_bound 進行二分搜索，找到數字的第一次出現位置。這樣可以大幅度降低查詢的時間複雜度。
- 優缺點：這種方法的優點是高效，時間複雜度為 O(log n)。但是需要理解並實現二分搜索或使用 STL 函數
lower_bound。
最終選擇的解法：
- 我最終選擇了 二分搜索 來解決這個問題。由於數列是有序的，二分搜索可以在 O(log n) 的時間內找到指定數字的位置，這在處理大數據量時非常有效。
代碼實現
lower_bound 寫法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
long long n, m; cin >> n >> m;
vector<long long> temp(n, 0);
vector<long long> filter_temp(m, 0);
for(long long i = 0; i < n; i++){
cin >> temp[i];
}
for(long long i = 0; i < m; i++){
cin >> filter_temp[i];
}
for(long long i = 0; i < filter_temp.size(); i++){
auto it = lower_bound(temp.begin(), temp.end(), filter_temp[i]);
if(i > 0) cout << " ";
if(it != temp.end() && *it == filter_temp[i]){
cout << it - temp.begin() + 1;
} else {
cout << -1;
}
}
}
|
二分搜尋寫法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
using namespace std;
int binarySearch(vector<int> &temp, int target) {
int left = 0, right = temp.size() - 1;
int result = -1;
while(left <= right){
int mid = left + (right - left) / 2;
if(temp[mid] == target) {
result = mid;
right = mid - 1;
} else if (temp[mid] > target){
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n, m; cin >> n >> m;
vector<int> temp(n, 0);
vector<int> filter_temp(m, 0);
for(int i = 0; i < n; i++){
cin >> temp[i];
}
for(int i = 0; i < m; i++){
cin >> filter_temp[i];
}
for(int i = 0; i < filter_temp.size(); i++){
int result = binarySearch(temp, filter_temp[i]);
if(i > 0) cout << " ";
result != -1 ? cout << result + 1 : cout << -1;
}
}
|
