0

私は5分以内にcollabeditに書いたコードを直接投稿しています（アルゴリズムの理解を含む）ので、効率の面で完全に楽しいリスクがありますが、経験豊富なスタックオーバーフローアルゴリズムの愛好家に聞いてみたいと思いました問題について;

基本的に、配列から重複する要素を削除します。私のアプローチ：基本的に、ハッシュテーブルとしてstd :: mapを使用し、値が割り当てられていない場合は、複製された配列の各要素に対して、新しい配列に追加します。割り当てられている場合はスキップしてください。最後に、一意の配列を返します。これが私のコードであり、面接の質問に関して私が尋ねている唯一のことは、私の解決策をより効率的にすることができますか？

#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<int>uniqueArr(int arr[],int size){
    std::map<int,int>storedValues;
    vector<int>uniqueArr;
    for(int i=0;i<size;i++){
        if(storedValues[arr[i]]==0){
            uniqueArr.push_back(arr[i]);
            storedValues[arr[i]]=1;
        }
    }
    return uniqueArr;  
}

int main()
{   
    const int size=10;
    int arr[size]={1,2,2,4,2,5,6,5,7,1};
    vector<int>uniArr=uniqueArr(arr,size);
    cout<<"Result: ";
    for(int i=0;i<uniArr.size();i++) cout<<uniArr[i]<<" ";
    cout<<endl;
    return 0;
}
4

4 に答える 4

4

まず第一に、マップは必要ありません。値を格納するのではなく、キーのみを格納する必要があるため、セットは概念的により正確です。

パフォーマンスに関しては、 a のstd::unordered_set代わりに aを使用することをお勧めしstd::setます。前者はハッシュされ、最良の場合は O(1) の挿入とルックアップを提供できますが、後者は二分探索ツリーであり、O のみを提供します。 (ログ n) アクセス。

vector<int> uniqueArr(int arr[], int size)
{
    std::unordered_set<int> storedValues;
    vector<int> uniqueArr;
    for(int i=0; i<size; ++i){
        if(storedValues.insert(arr[i]).second)
            uniqueArr.push_back(arr[i]);
    return uniqueArr;  
}

ただし、C++ 標準ライブラリをより広範囲に使用することが許可されている場合は、 and を使用して他の回答を検討することもできますがstd::sort、std::uniqueそれらは(上記の~O(n)ソリューションの代わりに) O(n log n)であり、の順序を破棄します要素。

より柔軟で標準駆動型のアプローチを使用したいが、複雑さが ~O(n) あり、要素の順序を破壊しない場合は、上記のルーチンを次の標準のようなアルゴリズムに変換できます。インタビューの簡単な質問としては、とてつもない質問です。

template<typename ForwardIterator>
ForwardIterator unordered_unique(ForwardIterator first, ForwardIterator last)
{
    typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
    std::unordered_set<value_type> unique;
    return std::remove_if(first, last, 
                          [&unique](const value_type &arg) mutable -> bool
                              { return !unique.insert(arg).second; });
}

std::uniqueその後、通常の消去削除方法のように適用できます。

std::vector<int> values(...);
values.erase(unordered_unique(values.begin(), values.end()), values.end());

ベクトルをコピーせず、事前にソートする必要もなく、一意の値を削除します。

于 2012-06-09T23:08:13.690 に答える
2

Since you are asking in terms of an interview question, I will say that you don't get the job.

const int size=10;
int arr[size]={1,2,2,4,2,5,6,5,7,1};

std::sort( &arr[0], &arr[size] );
int* new_end = std::unique( &arr[0], &arr[size] );

std::copy(
    &arr[0], new_end,
  , std::ostream_iterator< int >( std::cout, " " )
);

No temporary maps, no temporary vectors, no dynamic memory allocations, a lot less code written so its easier both to write and to mantain.

于 2012-06-09T22:52:06.540 に答える
1

インプレース削除は速度に優れています-次のようなものです（新しいサイズを返します）：

template <typename T, size_t N>
size_t keep_unique(T (&array)[N])
{
    std::unordered_set<T> found;
    for (size_t i = 0, j = 0; i < N; ++i)
        if (found.insert(array[i]).second))
            if (j != i) // (optional) avoid copy to self, as may be slower or unsupported by T
                array[j++] = array[i];
            else
                ++j;
    return j;
}

(より大きなオブジェクト、または安全にコピーできないオブジェクトの場合T*、unordered_set に s を格納する必要があり、より高速でスペース効率が高い場合があります。逆参照比較演算子とハッシュ関数も提供する必要があります。)

これがどのように機能するかを視覚化するには、次の入力を処理することを検討してください。

1  3  6  3  5  6  0  2  1
         <--+<----+  |
               <-----+

上記の矢印は、答えを生成するために必要な最小限のインプレース圧縮を表しています。

1  3  6  5  0  2

[i]上記のアルゴリズムは、 にあるすべての要素を調べて、 にコピーする必要がある場所 (および重複していない要素がいくつあるか) を追跡することで、まさにこれを行います[j]。

于 2012-06-11T07:03:38.010 に答える
1 
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> vec({1,2,3,2,4,4,5,7,6,6});
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    // vec = {1,2,3,4,5,6,7}
    return 0;
}
//works with C++11
// O(n log n)
于 2012-06-09T23:05:42.520 に答える