Willkommen alle!
Ich bin Oleg. Spezialisierung: C ++ / C / OS-Kernel / Treiber / Hardware / Netzwerke / eingebettet. Ich lebe und arbeite seit ungefähr anderthalb Jahren im Ausland. Jetzt in Finnland, davor gab es Polen. Sie erzählten mir von den Besonderheiten des Umzugs in beide Länder vor mir, wer interessiert ist - schreiben Sie, ich werde Ihre Fragen beantworten. Es wurde auch viel über das Leben in diesen Ländern geschrieben. Aber eines Tages werde ich meine Eindrücke von beiden in Form eines kostenlosen Aufsatzes präsentieren.
Jetzt möchte ich über ein Problem sprechen, das ich einen halben Tag lang gelöst habe, obwohl es sich nicht gelohnt hat. Und das Lustige ist, dass ich in Interviews einige ähnliche Probleme gelöst habe. Ich traf sie beim Graben eines meiner Heimprojekte.
Bei einer bestimmten Anzahl von Mengen von ganzen Zahlen unterschiedlicher Größe. Sie müssen die Zahlen finden, die in allen Sätzen außer einer enthalten sind. Der Index der Menge, in der das Element fehlt, ist ebenfalls erforderlich.
Angenommen, es gibt Mengen {1, 2, 3}, {3, 0, 4}, {5}. In diesem künstlichen Beispiel behauptet das Element {3}, das in der Null- und der ersten Menge vorhanden ist und in der zweiten Menge fehlt, ein Fund zu sein. Es kann auch als Menge {3, 2} geschrieben werden. Dieser Datensatz wird buchstäblich wie folgt entschlüsselt: Der Wert 3 fehlt in Satz 2. Eine weitere Bedingung: Es nehmen nur positive ganze Zahlen von 1 bis 64 teil. Die Elemente jedes Satzes sind eindeutig.
Grundsätzlich ist dies eine Art Verallgemeinerung des klassischen Interviewproblems. Letzteres wird wie folgt formuliert: Zahlen werden am Eingang eines bestimmten Programmblocks empfangen, Duplikate müssen abgeschnitten werden. Es kann auf elementare Weise mit dem Grundelement STL unordered_set gelöst werden. Es ist gut, weil es O (1) hat - konstante Suchzeit für kurze numerische Sequenzen. Im Rahmen einer begrenzten Aufgabe ist es in Geschmack und Farbe sehr angenehm für sich. Außerdem wird beim Hinzufügen eines Duplikats dieses einfach nicht hinzugefügt. In diesem Fall ist es auch nicht erforderlich, den Rückgabewert zu überprüfen. Das heißt, wir sparen drei Codezeilen, die ohnehin in der Implementierung der Vorlage enthalten sind. Da der Zahlenbereich in meinem Projekt jedoch begrenzt ist, können Sie überhaupt darauf verzichten. Ja, wenn Sie den Zahlenbereich erweitern, muss unordered_set oder ähnliches verwendet werden.
Stellen Sie der Einfachheit halber die Anzahl der Sätze gleich 3 ein. Der Satz wird in einem Vektor oder STL-Vorlagenvektor <Vektor> gespeichert. Das Ergebnis ist eine Menge von Paaren nicht negativer Zahlenvektor <Paar <int, int >>. In einem Paar ist an erster Stelle das Element selbst, an zweiter Stelle der Index der Menge, wo es nicht ist.
void PrepareData(const vector<vector<int> >& src, vector<pair<int, int> >& res)
{
vector<pair<int, int> > data(MAX); //
for(unsigned i(0); i < src.size(); ++i)
{
const auto& rf(src[i]);
for(unsigned j(0); j < rf.size(); ++j)
{
ASSERT(((0 < rf[j]) && (MAX > rf[j])) && "!!! An invalid data !!!");
++data[rf[j]].first; //
data[rf[j]].second += i; //
}
}
auto fs(((src.size() - 1) * src.size()) >> 1); //
for(unsigned i(0); i < data.size(); ++i) //
{
if(data[i].first == src.size() - 1) //
{
pair<int, int> cur{i, 0}; //
cur.second = fs - data[i].second; // ,
res.push_back(cur);
}
}
}1)
2) . . , .
3) data . , , ,
4) , (a[1] + a[n]) * n / 2
5) , ,
6) , ,
Das ist alles, ein halber Tag voller Qualen. Der Code gibt nicht vor, schön zu sein. Der Wunsch bestand nur darin, eine Idee oder einen Ansatz zur Lösung solcher Probleme vorzustellen. Besonderer Dank geht an Ilyawataru, der mir empfohlen hat, auf die Optimalität meiner Algorithmen zu achten.
Code-Link https://yadi.sk/d/F2dLt6v_uvjKdQ