【C++】vectorが別のvectorのサブセットであるか否かを判断する

C++はpythonがissubsetメソッドを持っていないように、1つの要素が別の要素のサブセットであるかどうかを判断するために使用され、自分で1つ書く必要がありますが、vector 1の1つの要素がvector 2に属しているかどうかを判断することはできません.このサブセットの最も基本的な定義は判断します.これは、vector 1の長さがmであれば、vector 2の長さがnであれば、複雑さが大きすぎます.時間の複雑さはO(m*n)まで長く、要素が多くなると致命的であり、vectorが別のvectorのサブセットであるかどうかを次のように判断することができる.

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
bool isSubset(vector<int> v1, vector<int> v2){
     
	int i=0,j=0;
	int m=v1.size();
	int n=v2.size();
	if(m<n){
     
		return 0;
	}
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	while(i<n&&j<m){
     
		if(v1[j]<v2[i]){
     
			j++;
		}
		else if(v1[j]==v2[i]){
     
			j++;
			i++;
		}
		else if(v1[j]>v2[i]){
     
			return 0;
		}
	}
	if(i<n){
     
		return 0;
	}
	else{
     
		return 1;
	}
}
int main(){
     
	vector<int> v1,v2;
	v1.push_back(3);v1.push_back(2);v1.push_back(1);
	v2.push_back(1);v2.push_back(2);
	cout<<isSubset(v1,v2)<<endl;
	vector<int> v3,v4;
	v3.push_back(3);v3.push_back(1);v3.push_back(2);
	v4.push_back(1);v4.push_back(4);v4.push_back(4);
	cout<<isSubset(v3,v4)<<endl;
	vector<int> v5,v6;
	v5.push_back(3);v5.push_back(1);v5.push_back(2);v5.push_back(3);
	v6.push_back(1);v6.push_back(2);
	cout<<isSubset(v5,v6)<<endl;
	return 0;
}

プログラム設定は、v 2={1,2}がv 1={3,2,1}のサブセットであるか否か、v 4={1,4,4}がv 3={3,1,2}のサブセットであるか否か、v 6={1,2}がv 5={3,1,2,3}のサブセットであるか否かを判定する3つの例をテストし、実行結果は以下の通りである.
アルゴリズムの基本思想は以下の通りであり,まず2つの配列を独自のsort法で迅速に並べ替える.更に2つのカーソルi,jで同時に遊走して判断し、以下の状況に分けられる.
このソートにより,vectorが別のvectorのサブセットであるか否かを判断することが迅速に完了し,最後の時間複雑度はO(mLogm+nLogn)のみであり,線形対数次は少なくとも2乗次より1段階少ない.時間は主に高速ソートの線形対数次に費やされた.
テキストリンク:https://blog.csdn.net/yongh701/article/details/51423030