Kiểm tra các phần tử có trong mảng (list) nhanh nhất

#1

Các bạn cho mình hỏi cách nào để kiêm tra các phần tử trong mảng mảng (list) tối ưu và nhanh không à.
cụ thể:
Mảng A: [‘cam’, ‘quyt’, ‘xoai’]
Mảng B [‘dua’, ‘saurieng’, ‘cam’, ‘quyt’, ‘bo’, ‘chuoi’, ‘xoai’]

giờ kiemr tra xem các phần tử ở mảng A có tồn tại trong mảng B không.
Cách đọc từng phần tử thì có vẻ không tối ưu và nhanh lắm, vì mảng B của mình có thể có nhiều phần tử lắm.

Nhờ các bạn chỉ mình cách làm với.
Cảm ơn :smiley:

#2

up :smile: :smiley: :smiley: :disappointed:

#3

Đọc từng phần tử và hi vọng vào tốc độ xử lý của máy tính :sweat:

1 Like
#4

Ý bạn có phải làm xét xem tập hợp A có phải là con của tập hợp B (kiểm tra xem tất cả các phần tử của A có tồn tại hết trong B hay không) ? Nếu là kiểm tra theo kiểu tập hợp thì bạn thử theo cách của mình:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool check(vector<int> a, vector<int> b)	{
	
	int ia = 0, ib = 0; //index of vector a and index of vector b
	
	while(b[ib] < a[ia] && ib < b.size()) 
		ib++; //move the index of vector b to position
				//where a[ia] = b[ib]
	
	//first of all, we check if the next element of vector b
	//whether equal with the first element of vector a
	//if not, return false
	if(b[ib] != a[ia])
		return false;
		
	//next, we check if each respective element whether equal or not
	while(ia < a.size() && ib < b.size())
	{
		if(a[ia] != b[ib])
			return false;
		else
			ia++, ib++;
	}
	
	return true;
}

int main() {
	
	vector<int> a = { 4,2,3 };
	vector<int> b = { 1,2,3,4,5,6 };
	
	std::sort(a.begin(), a.end());
	std::sort(b.begin(), b.end());
	
	cout << check(a,b);
	
	return 0;
}

Vì kiểm tra tập hợp, nên mình đảm bảo là đã loại bỏ các phần tử bị trùng trong mỗi vector, và vector con cần kiểm tra phải có số lượng phần tử nhỏ hơn vector kia.
Bạn sắp xếp mảng kiểu string tương tự như kiểu số nguyên.

1 Like
#5

Dùng unordered_set trong C++11 bản chất của nó là 1 hash table nên thời gian tìm kiếm là O(1)

####code tham khảo

#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    vector<string> A={"cam", "quyt", "xoai"};
    vector<string> B={"dua", "saurieng", "cam", "quyt", "bo", "chuoi", "xoai"};
    unordered_set<string> set_B;
    
    for(auto str: B){
        set_B.insert(str);
    }
    for(auto str_A:A){
        if(set_B.find(str_A)!=set_B.end()){
            cout<<str_A<<" found!"<<endl;
        }else{
            cout<<str_A<<" not found!"<<endl;
        }
    }
    
    return 0;
}
1 Like
#6

Cảm ơn bác.
Mà cái của e làm là C#.

#7

Thế thì dùng Dictionary

#8

C# có hàm như vậy k bác

#9

Sử dụng constain hay constainof có phải nhanh không.

#10

Mấy cách trên cũng là dùng loop đọc từng phần tử còn gì :sweat:

#11

C# có kiểu dữ liệu HashSet tương tự

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