c++ - 2D 配列の列で重複を検出する

Question

2D 配列を通過し、各列がすべて個別の数値を持つことを保証するアルゴリズムが必要です。配列内に重複が見つかった場合は、乱数に置き換える必要があります。乱数も一意性を維持する必要があります。

乱数を入れると、列全体が一意になるはずです。

O(N) ソリューションも取得できますか?

Answer 1

私が考えることができる最善の方法はunordered_map<int,bool>、各列を作成し、列を反復処理し、初めて数値が表示された場合はマップをtrueに設定し、値がすでにtrueの場合は、それを乱数に置き換えることです。 . 次に、マップ内の乱数を確認し、同じことを行います。これもだまされている場合は、もう一度乱数に置き換える必要があります。このアルゴリズムは線形時間で実行されますが、乱数が重複する可能性があるため、無限に実行される可能性があります。

疑似コード

2d_array // assume M rows by N cols
array_of_hashtables // N length
for each col
    for each row
       if array_of_hashtables[2d_array[row][col]] == false
           set it to true
       else
           do
               set 2d_array[row][col] to random
           while array_of_hashtables[2d_array[row][col]] == true
    end
end

疑似コードを書くのが好きというわけではありませんが、これはほぼ正しいです

Answer 2

念のため、Alexandru Barbarosieのソリューションの実装を次に示します。

#include <iostream>
#include <set>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    int L = 3;
    int W = 3;
    int R = 3;    
    int a[L][W];    
    srand(time(NULL));     
    for (int i = 0; i < L; i++)
    {
        for (int j = 0; j < W; j++)
        {
            a[i][j] = rand() % R + 1;
            cout << a[i][j] << " ";
        }
        cout << endl;
    }    
    cout << endl;

    set<int> s;    
    int n = 0;    
    for (int j = 0; j < W; j++)
    {
        for (int i = 0; i < L; i++)
        {
            s.insert(a[i][j]);
            if (s.size() != n)
                n = s.size();
            else
                a[i--][j] = rand() % R + 1;
        }
        s.clear();
        n = 0;
    }

    for (int i = 0; i < L; i++)
    {
        for (int j = 0; j < W; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }
}