[Mảng 1 Chiều Cơ Bản]. Bài 37. Tìm kiếm trong mảng 1 chiều - 28tech Online Judge

[Mảng 1 Chiều Cơ Bản]. Bài 37. Tìm kiếm trong mảng 1 chiều

Gửi bài giải

Danh sách bài nộp

Bài nộp tốt nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Java 4.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

Nguồn bài:

28Tech

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng A[] gồm N phần tử, bạn hãy kiểm tra xem giá trị X có xuất hiện trong mảng không?

Gợi ý : Dùng mảng đánh dấu để mỗi test case chỉ mất O(1) thay vì tìm kiếm tuyến tính sẽ mất O(N)

Đầu vào

Dòng 1 là N : số phần tử trong mảng

Dòng 2 là N số trong mảng viết cách nhau 1 dấu cách

Dòng 3 là T : Số test case

T dòng tiếp theo mỗi dòng là số nguyên X

Giới hạn

1<=N<=10^6

0<=A[i]<=10^7

1<=T<=10^4

0<=X<=10^7

Đầu ra

Đối với mỗi test case in ra YES nếu X xuất hiện trong mảng, ngược lại in NO.

Ví dụ :

Input 01

9
2 41 21 28 27 3 49 22 2 
5
3
27
15
15
19

Output 01

YES
YES
NO
NO
NO

Bình luận

Hãy đọc nội quy trước khi bình luận.

-5

khuemih đã bình luận lúc 26, Tháng 8, 2024, 9:43

co cai chem chep

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-1

doanbang042 đã bình luận lúc 14, Tháng 9, 2024, 4:22

bạn cho mình hỏi code này của mình sao lại TLE ạ?

-1
doanbang042 đã bình luận lúc 14, Tháng 9, 2024, 4:22
include <stdio.h>

include <math.h>

int dem[1000001]; int ba(int a[],int n,int x){ int max=-1e9,cnt=0; for(int i=0;i<n;++i){ if(a[i]==x){ dem[a[i]]=1; if(a[i]>max){ max=a[i]; }

} } for(int i=0;i<n;++i){ if(dem[a[i]]==1){ cnt++; dem[a[i]]=0; } } if(cnt>0){ return 1; }else{ return 0; }

} int main(){ int n; scanf("%d",&n); int a[n]; for(int i=0;i<n;++i){ scanf("%d",&a[i]); } int t; scanf("%d",&t); int x; for(int i=1;i<=t;++i){ scanf("%d",&x); if(ba(a,n,x)){ printf("YES\n"); }else{ printf("NO\n"); } } }

-1

duongnc_pt đã bình luận lúc 31, Tháng 10, 2024, 12:54

Bạn có thể xem hoặc tìm hiểu thuật toán 'Mảng cộng dồn' nhé!

Theo như code của bạn thì bị quá thời gian do do sử dụng tìm kiếm tuyến tính(Duyệt từ 0 -> n - 1) => độ phức tạp tốn O(n)

Vì vậy mỗi testcase bạn phải duyệt ~10^6~ lần. Do vậy độ phức tạp của bạn là ~10^4~ * ~10^6~(Vượt qua mức an toàn là ~10^8~

-8
namduongit đã bình luận lúc 20, Tháng 7, 2024, 2:02
include <bits/stdc++.h>

using namespace std;

int main () { int n; cin >> n; int *arr = new int[n]; int *testCaseArray = new int[10000001]; for (int i = 0; i < n; i ++) { cin >> arr[i]; testCaseArray[arr[i]] ++; } int testCase; cin >> testCase; int cons; for (int i = 0; i < testCase; i ++) { cin >> cons; if (testCaseArray[cons] > 0) { cout << "YES" << endl; testCaseArray[cons] --; } else cout << "NO" << endl; }

delete[] arr;

}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.