Intersection between 2 arrays

hi,

sind die laufzeit analysen beider algorithmen korrekt?

// Overall Complexity: O(n + m)
vector<int> get_intersection_sorted(vector<int> &arr1, vector<int> &arr2) {
	// we assume the arrays to be pre-sorted
	typedef std::unordered_map<int, int> unordered_map;
	unordered_map ht;
	unordered_map::iterator it;
	std::vector<int> out;

	for(int i = 0; i < arr1.size(); i++) {
		ht[arr1[i]]++; // O(n) ... n = length of arr1
	}

	for(int i = 0; i < arr2.size(); i++) { // O(m) ... m = length of arr2
		it = ht.find(arr2[i]);  // O(1)
		if(it != ht.end()) {
			out.push_back(arr2[i]);
			(*it).second -= 1;
		}
	}

	return out;
}

// Overall Complexity: O(n log n + m * log n)
vector<int> get_intersection_unsorted(vector<int> &arr1, vector<int> &arr2) {
	// we assume the arrays to be non sorted
	std::sort(arr1.begin(), arr1.end()); // O(n log n) ... n = length of arr1 ... i assume this to be quicksort!?
	std::vector<int> out;

	for(int i = 0; i < arr2.size(); i++) {
		if(std::binary_search(arr1.begin(), arr1.end(), arr2[i])) { // O(m * log n) ... m = length of arr2
			out.push_back(arr2[i]);
		}
	}

	return out;
}

der erste algo ist auch für non-sorted arrays

volkard

Jo, die Komplexitäten halte ich für richtig. Daß der naheliegende Algorithmus nicht dabei ist, ist Absicht?

inplace algorithmus?

// Overall Complexity: O(n log n + m * log n)
void get_intersection_unsorted(vector<int> &arr1, vector<int> &arr2) {
	// we assume the arrays to be non sorted
	std::sort(arr1.begin(), arr1.end()); // O(n log n) ... n = length of arr1
	std::vector<int>::iterator it = arr2.begin();

	while(it != arr2.end()) {
		if(!std::binary_search(arr1.begin(), arr1.end(), *it)) { // O(m * log n) ... m = length of arr2
			it = arr2.erase(it);
		}
		else {
			it++;
		}
	}
}

volkard

geri1 schrieb:

inplace algorithmus?

Nö. mergen.

while(
  if(*a<*b)
    ++a;
  else if(*b<*a)
    ++b;
  else{
    outpush(*a);
    ++a,++b;
  }

ist aber langsamer als binary sort!?

volkard

geri1 schrieb:

ist aber langsamer als binary sort!?

nö, ist offensichtlich schnell.

edit: binary sort?

meinem algo ist: O(n log n + m * log n) 

Volkard: O(n) ?