leetcodeブラシ問題--基礎配列--2つの配列の交差(C)

は、2つの配列を与え、それらの交差を計算するために関数を記述する.例1:入力:nums 1=[1,2,1]、nums 2=[2,2]出力:[2,2]例2:入力:nums 1=[4,9,5]、nums 2=[9,4,9,8,4]出力:[4,9]出力結果の各要素の出現回数は、要素が2つの配列に現れる回数と一致することを示す.出力結果の順序を考慮しなくてもよい.

思想:(1)2つの配列を並べ替えO(nlgn)し,順次O(n)比較転送する.時間的複雑度はO(nlgn),空間的複雑度はO(1)であったが,元の配列を破壊した.ソート関数は一般的に各言語が持つ関数を使用する効率が高いので、ここではデフォルトで2つの配列がソートされています.

int intersect(int* nums1, int nums1Size, int* nums2, int nums2Size){
	int i=0, j=0;
	int count=0;
	if(nums1Size nums2[j])
			j++;
		else
			i++;
	}
	return count;
} 

(2)暴力解法.短い配列を基準として、その中の要素を一つ一つ取り出して長い配列の中の要素と比較し、同じであれば格納し、その要素がある長い配列の位置をマークして重複を避ける.時間複雑度O(n^2)、空間複雑度O(n)は、元の長い配列で空間を使用したくない場合は修正し、比較できない値に変更することができる.これで元の配列が破壊されます.

tersect(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int count = 0;
    if(nums1Size

(3)ハッシュ表.2つの配列AとBを新しい配列に遍歴し、統計的に繰り返される数字でよい.この時間複雑度はO(n)、空間複雑度O(m)である.この要求配列内の数字の範囲は既知で大きくない.同じくJAVAの中にHashMapがあります.