-1

I would like an algorithm that goes through a 2D array and guarantees that each column has all distinct numbers. If a dupe is found in the array it should be replaced with a random number. The random number must also preserve the uniqueness.

If we put a random number, the whole column, should be unique.

is it possible to get an O(N) solution too ?

4

3 回答 3

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

不是编写伪代码的忠实粉丝，但这是正确的

于 2013-07-23T17:41:55.957 回答
1

在检查集合大小的同时，制作一个std::set并逐步插入每列的元素。如果大小发生变化，则插入的值不是重复的，如果它只是随机化一个值并将其再次添加到集合中。如果大小发生变化，您可以继续。

于 2013-07-23T17:52:44.923 回答
0

顺便说一句，这里是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;
    }
}
于 2013-07-23T18:27:35.827 回答