Code bài xác định dãy số có lặp hay không bị chạy quá thời gian với test case khoảng 100k

#1 
#include<iostream>
#define Max 200000
using namespace std;
	void Nhapday(int a[],int n){
		for(int i=0;i<n;i++)
			cin>>a[i];
		}
	void Kiemtra(int a[],int n){
		int temp=1;
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
				if(a[i]==a[j])
				{
					temp=0;
					break;
				}
			}
		if(temp==0) cout<<"Yes";
		else if(temp==1)cout<<"No";			 
						
		}	
	int main(){
		int n,a[Max];
		cin>>n;
		Nhapday(a,n);
		Kiemtra(a,n);
		return 0;
		}

Đề bài yêu cầu tìm xem dãy sô đã nhập có số hạng nào trùng nhau không, nếu có in ra “Yes” ngược lại “NO”.Đoạn code trên của em chỉ chạy được với dãy số lượng số ít với test 100k số thì bị time limit.Có cách nào khác hay chỉnh lại đoạn code trên đk k ạ?

1 Like
#2

Độ phức tạp O(n^2) thì chỉ chạy đc với n tầm 3*10^3 đổ lại thôi, to hơn chết ngay.

Về cơ bản cũng chỉ là kiểm tra xem có tồn tại 2 số nào bằng nhau thôi nên bạn thử sort xem.

2 Likes
#3

Thanks bạn nha mk làm đk rồi!!

1 Like
#4

Vấn đề là do bạn chọn sai data structure. Với dữ liệu nhỏ thì dùng Array, khi dữ liệu lớn thì dùng Tree.

2 Likes
#5

Không hẳn, có xóa sửa thì mới nên dùng tree, còn ghi 1 lần thì dùng mảng thôi.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?