VT04 - Tìm kiếm trong mảng
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho mảng số nguyên ~A~ có ~n~ phần tử, hãy tìm kiếm xem trong mảng có xuất hiện phần tử ~x~ hay không?
Input
- Dòng 1 là số nguyên dương ~n~ (số lượng phần tử của mảngm ~n \le 10^6~) và số nguyên ~x~ (~|x| \le 10^9~) là giá trị cần tìm
- Dòng tiếp theo là ~n~ số nguyên là các phần tử của mảng (~|a_{ij}| \le 10^9~)
Output
- Nếu ~x~ xuất hiện ít nhất 1 lần trong mảng, in ra
YES - Nếu ~x~ không có trong mảng, in ra
NO
Sample
Input #1
5 3
1 2 3 4 5
Output #1
YES
Bình luận
c++
dùng kiểu gắn cờ thôi mn
include <bits/stdc++.h>
using namespace std;
int main(){
int n,x,flag=0;cin>>n>>x;
int a[n];
for (int i=0;i<n;i++){
cin>>a[i];
}
for (int j=0;j<n;j++){
if (a[j]==x){
cout<<"YES";
flag=1;
}
}
if (flag==0) cout<<"NO";
return 0;
}
Tim kiem trong mang
n,x = [int(x) for x in input().split()]
A = list(map(int, input().split()))
if A.count(x)!=0:
else:
Bài này phải dùng chặt nhị phân
Bạn có thể tham khảo 1 code ko dùng duyệt trâu nè
include <bits/stdc++.h>
define int long long
using namespace std;
int n, nf, nb; bool found;
void solve() {
} main() {
}
Ở đây khi mình nhập vô thì mình so sánh luôn giúp giảm thời gian ko phải for lại hay duyệt nhị phân đó AC 4 câu nha bạn
Bài này dùng gì cx được vì n cùng lắm cx chỉ có 10^6 nên có thể vẫn ac đc nhưng nên tìm 1 số cách nhanh hơn chứ duyệt trâu thì lâu lắm
Vector thì chậm hơn mảng thường khoảng 2 - 3 lần đấy bạn
Bài này thì xài chặt nhị phân có thể là nhanh nhất rồi vì ~log_2(10^6)~ khoảng 20 thôi nên nếu n = ~10^9*10^3~ thì cx có gần 40 và bài này cũng sort được chỉ mất ~log_2(n)~ thôi nên cách này ok nha
sort chi nlog(n) duoc thoi chu log(2,n) kieu chi vay ban
Chặt chi nếu dùng C++ thì có thể xài multiset, hoặc xài duyệt mảng theo cách bth, vector hàm count....
ai co dap an dang len di
Bạn có thể tham khảo của mình. Mình code bằng ngôn ngữ C.
include <stdio.h>
int main() { int n, x, i; scanf("%d", &n); scanf("%d", &x); if (n > 1000000 || x > 1000000000 || x < -1000000000) { return 1; } int a[n]; for (i = 0; i < n; i++) { scanf("%d", &a[i]); } int count = 0; for (i = 0; i < n; i++) { if (a[i] == x) { count++; } } if (count >= 1) { printf("YES"); } else { printf("NO"); } return 0; }
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
k qua nhỉ
include <iostream>
using namespace std; int main(){ int m; cin >> m; int a[m]; int n; cin >> n; for(int i=0; i<m; i++){ cin >> a[i]; } bool found = false; for(int i=0; i<n; i++){ if(n == a[i]){ found = true; break; } } if(found){ cout << "YES"; } else{ cout << "NO"; } return 0; }