Selamat datang semuanya!
Saya Oleg. Spesialisasi: Kernel C ++ / C / OS / driver / perangkat keras / jaringan / tertanam. Saya telah tinggal dan bekerja di luar negeri selama sekitar satu setengah tahun. Sekarang di Finlandia, sebelumnya ada Polandia. Mereka bercerita tentang keanehan pindah ke kedua negara sebelum saya, siapa yang tertarik - tulis, saya akan menjawab pertanyaan Anda. Banyak juga yang telah ditulis tentang kehidupan di negara-negara ini. Namun suatu saat nanti saya akan menyajikan kesan saya terhadap keduanya dalam bentuk esai gratis.
Sekarang saya ingin berbicara tentang masalah yang telah saya selesaikan setengah hari, meskipun itu tidak sepadan. Dan lucunya adalah saya memecahkan beberapa masalah serupa dalam wawancara. Saya bertemu dengannya saat menggali salah satu proyek rumah saya.
Jadi, diberikan sejumlah set bilangan bulat dengan ukuran berbeda. Anda perlu menemukan angka-angka yang ada di semua set kecuali satu. Indeks himpunan yang elemennya hilang juga diperlukan.
Misalkan ada set {1, 2, 3}, {3, 0, 4}, {5}. Dalam contoh buatan ini, elemen {3}, yang ada di nol dan set pertama dan tidak ada di set kedua, mengklaim sebagai penemuan. Ini juga dapat ditulis sebagai satu set {3, 2}. Secara harfiah, record ini diuraikan sebagai berikut: nilai 3 tidak ada di set 2. Satu syarat lagi: hanya bilangan bulat positif dari 1 hingga 64 yang berpartisipasi.Elemen dari setiap set adalah unik.
Pada dasarnya, ini adalah semacam generalisasi dari masalah wawancara klasik. Yang terakhir dirumuskan sebagai berikut: nomor diterima pada input dari blok program tertentu, itu perlu untuk memotong duplikat. Ini dapat diselesaikan dengan cara dasar menggunakan STL unordered_set primitive. Ini bagus karena memiliki O (1) - waktu pencarian konstan untuk urutan bilangan pendek. Dalam kerangka tugas terbatas, cukup menyenangkan dalam rasa dan warna. Selain itu, saat menambahkan duplikat ke dalamnya, itu tidak akan menambahkannya. Dalam kasus tersebut juga tidak perlu memeriksa nilai pengembalian. Artinya, kami memiliki penghematan tiga baris kode, yang tetap terkandung dalam implementasi template. Tetapi, karena proyek saya memiliki jumlah terbatas, Anda dapat melakukannya tanpa itu sama sekali. Ya, jika Anda memperluas rentang angka, maka unordered_set, atau semacamnya, harus digunakan.
Untuk mempermudah, mari kita setel jumlah set ke 3. Himpunan disimpan dalam vektor, atau STL template vector <vector>. Hasilnya adalah himpunan pasangan vektor bilangan non-negatif <pair <int, int >>. Dalam sebuah pasangan, pertama-tama adalah elemen itu sendiri, di tempat kedua adalah indeks dari himpunan yang bukan.
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) , ,
Itu saja, setengah hari siksaan. Kode itu tidak berpura-pura cantik. Keinginannya hanya untuk mempresentasikan ide, atau pendekatan untuk memecahkan masalah tersebut. Terima kasih khusus kepada Ilyawataru, yang merekomendasikan agar saya memperhatikan optimalitas algoritme saya.
Tautan kode https://yadi.sk/d/F2dLt6v_uvjKdQ