すべてを歓迎する！
オレグです。専門分野：C ++ / C / OSカーネル/ドライバー/ハードウェア/ネットワーク/組み込み。私は海外に住み、約1年半働いています。今フィンランドでは、その前にポーランドがありました。彼らは、興味を持っている私の前に両国に引っ越すことの特徴について私に話しました-書いてください、私はあなたの質問に答えます。これらの国々での生活についてもたくさん書かれています。しかし、いつか私は無料のエッセイの形で両方の私の印象を提示します。
それでは価値がなかったのですが、半日かけて解決した問題についてお話したいと思います。そして面白いのは、インタビューでいくつかの同様の問題を解決したことです。私は私の家のプロジェクトの1つを掘っている間に彼女に出くわしました。
したがって、異なるサイズの整数のセットの特定の数が与えられます。 1つを除くすべてのセットにある番号を見つける必要があります。要素が欠落しているセットのインデックスも必要です。
セット{1、2、3}、{3、0、4}、{5}があるとします。この人工的な例では、ゼロと最初のセットに存在し、2番目のセットには存在しない要素{3}は、検索結果であると主張します。セット{3、2}として書くこともできます。文字通り、このレコードは次のように解読されます。値3がセット2に存在しません。もう1つの条件：1から64までの正の整数のみが参加します。各セットの要素は一意です。
基本的に、これは古典的なインタビュー問題の一種の一般化です。後者は次のように定式化されます。プログラムの特定のブロックの入力で番号が受信されるため、重複をカットする必要があります。これは、STLunordered_setプリミティブを使用して基本的な方法で解決できます。 O（1）-短い数のシーケンスの一定の検索時間があるので、これは良いことです。限られた仕事の枠内で、味と色がとても心地よいです。その上、それに複製を追加するとき、それは単にそれを追加しません。その場合も戻り値を確認する必要はありません。つまり、テンプレートの実装に含まれている3行のコードを節約できます。しかし、私のプロジェクトの数は限られているので、それなしで行うことができます。はい、数値の範囲を拡大する場合は、unordered_setなどを使用する必要があります。
簡単にするために、セットの数を3に設定しましょう。セットはベクトル、またはSTLテンプレートベクトル<vector>に格納されます。結果は、非負の数のペアのセットvector <pair <int、int >>です。ペアでは、最初は要素自体であり、2番目はそうでないセットのインデックスです。
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) , ,
それがすべて、半日の苦痛です。コードは美しいふりをしていません。そのような問題を解決するためのアイデア、またはアプローチを提示することだけが目的でした。イリヤに感謝しますわたる、私のアルゴリズムの最適性に注意を払うことを勧めた人。