Programmiercontest...

[Walli]

Jo, ich mach da schonmal mit wenn ich Langeweile habe. Manchmal ist die Auswertung der Ergebnisse allerdings nicht ganz nachvollziehbar.

[HumeSikkins]

Hallo,
das Bewertungskriterium dieser Aufgabenstellung findet ich persönlich mal wieder äußerst dämlich. Was genau bringt einem denn "code brevity"?

Die Aufgabe an sich finde ich aber interessant.
Was würdet ihr für einen Algorithmus verwenden?
Ich habe bisher über drei Ansätze nachgedacht:
1. Triviale Lösung -> Zwei Schleifen: n^2
2. Arrays sortieren + 1 Schleife zum Vergleichen: 2 * (nlogn) + n
3. Bit-Vektor der Größe size = (max(a,b) / + 1: 2n + 2size

Wie würdet ihr vorgehen?

[Shade Of Mine]

MaSTaH schrieb:

Jo, ich mach da schonmal mit wenn ich Langeweile habe. Manchmal ist die Auswertung der Ergebnisse allerdings nicht ganz nachvollziehbar.

jo, vorallem dass die Testdaten nicht bekanntgegeben werden ist doof. Vorallem wenn es um speed geht.

Soll ich den Algo dann für <1000 Elemente optimieren, oder lieber für größere Elemente? etc...

IMHO sind die Daten einfach zu wenig...

[Bashar]

HumeSikkins schrieb:

Was genau bringt einem denn "code brevity"?

Spaß z.B.

[CarstenJ]

Sagt ihr mir mal bitte, ob es im Prinzip einfach ist, ein Array auf doppelte Einträge zu überprüfen? Ich schaffe es nicht, und wäre für Hilfe dankbar....irgendnen Ansatz, irgendnen Tipp, irgendwas, das mich weiterbringt.

[HumeSikkins]

Sagt ihr mir mal bitte, ob es im Prinzip einfach ist, ein Array auf doppelte Einträge zu überprüfen?

Was genau meinst du mit überprüfen? Nur eine Ja/Nein-Frage oder brauchst du alle Doppelten?

Zwei spontane Möglichkeiten für Ja/Nein:
1. Array sortieren, dann paarweise Vergleichen.
2. Zwei for-Schleifen. Die äußere geht von i = [0..n), die innere von j = [i+1..n).
Falls array[i] == array[j] -> Duplikat.

[Bashar]

3. Array-Elemente in eine Menge (Hashtable oder Baum (std::set)) eintragen, dabei prüfen ob schon vorhanden.

[HumeSikkins]

Hallo,
ich hätte da auch gerade mal ein Problem.
Gegeben:
sortiertes Array mit N Elementen (a1..aN mit ai <= ai+1)

Gesucht:
Array a1,..,ak,ak+1,..an mit ai < ai+1 für i <= k und ai <= ai+1 für i > k.

Dabei soll sowohl das Array transformiert werden, als auch der Index von (oder ein Zeiger auf) ak+1 geliefert werden.

Sprich: Alle Duplikate sollen nach hinten verschoben werden. Ihre Reihenfolge soll zusätzlich sortiert sein.

Beispiel:
Eingabe: a[] = {1, 2};
Ausgabe: a = {1,2} und k + 1 = 2

Eingabe: a[] = {1, 1, 2, 2};
Ausgabe: a = {1,2, 1, 2} und k + 1 = 2

Eingabe: a[] = {1,1,2,2,2,3,3,4};
Ausgabe: a = 1, 2, 3, 4, 1, 2, 2, 3 und k + 1 = 4

Meine Frage:
Lässt sich das nur durch Tauschen der Elemente implementieren. Sprich ohne temoporäres Array und ohne das man am Ende einfach die Duplikate sortiert?

Meine Lösung benötigt z.B. eine explizite Sortierung:

template <class FwdIter>
FwdIter uniqueImpl(FwdIter begin, FwdIter end)
{
	if (begin == end) return begin;
	FwdIter next = begin;
	FwdIter put = next;
	while (next != end)
	{
		while (next != end && *next == *put)
			++next;
		++put;
		if (next == end)
			return put;
		swap(*put, *next);
		++next;
	}
	return ++put;
}

template <class FwdIter>
FwdIter uniqueWithSort(FwdIter begin, FwdIter end)
{
	FwdIter newEnd = uniqueImpl(begin, end);
	sort(newEnd, end);
	return newEnd;
}

[defob]

hmm
naja angenommen man macht die sache von hinten her..
dann wuerde man fuer 1,1,2,2,2,2,3,3,4
=> 1,2,2,3,1,2,3,4
erhalten!
jetz drehen wir das ding bei put (zeigt auf 1) und voilá

1,2,3,4,1,2,2,3

[defob]

sry das war falsch
1,3,2,2,2,1,2,3,4 kommt natürlich raus..
hmm..