間の最短距離を見つける、整数A = [、、...、_N]いくつかの配列を指定し、配列

Question

に等しい要素の任意の対の間の最短距離を見つけます _IとI_{が JとI！= jで=（またはそのようなインデックスが存在しないことを示す）}よう _J。

だから、配列が同じ要素を探し、適切最小距離の更新を反復含む、C++でナイーブO（N ）アプローチを実装した：これはうまく機能

#include <vector> 
#include <climits> 
#include <algorithm> 

int MinPair(const std::vector<int>& nums) 
{ 
    int ret = std::numeric_limits<int>::max(); 
    for(int i = 0; i != nums.size(); ++i) 
    { 
     for(int j = 0; j != i; ++j) 
     { 
      if(nums[i] == nums[j]) 
       ret = std::min(ret, i - j); 
     } 
    } 

    if(ret == std::numeric_limits<int>::max()) 
     return -1; 

    return ret; 
} 

、しかし私はより効率的な実装について、std :: mapが関与していると言われました。すなわち、入力配列を通り、マップ内に要素の最初の出現を格納し、後続の出現ごとに、その出現とマップ内のその要素の最初の索引との間の距離を見つけることができます。その距離が現在の最小値よりも小さい場合は、その最小値を更新します。

しかし、私はどのようにしてこれがより効率的であるか見ることができません。時間の複雑さを考慮すると、入力配列（O（n））を調べ、要素が最初に出現するかどうかを識別するためにstd :: map :: findを使用する必要があります。 O（n ）の複雑さを与えます。スペースの複雑さのために、配列/ベクトルに加えてマップを格納する必要があります。私はここで何が欠けているのですか？

編集：私は誤ってmap :: findがO（n）だったと仮定しました。挿入と検索操作は実際にはO（log n）であり、バイナリ検索のようなものを使って基本的な実装を仮定してもすぐに見ることができます。

Answer 1

私はもともと、grigorで言及されたソリューションに類似したコーディングソリューションを投稿しました。そして、最良のケースと平均の場合、O（N）時間ですべてが機能するようにする明確な最適化があることを認識しました。

typedef pair<bool, int> LastPositionFound; 

int MinPair(const std::vector<int>& nums) 
{ 
    unordered_map<int, LastPositionFound> table; // maps value found in array to the last position that value was seen at. 
    int best_distance = -1; 

    for (size_t index = 0; index < nums.size(); index++) 
    { 
     int value = nums[index]; 
     LastPositionFound& lpf = table[value]; // returns {false,0} if not found 
     if (lpf.first) 
     { 
      int distance = index - lpf.second; 
      if ((distance < best_distance) || (best_distance == -1)) 
      { 
       best_distance = distance; 
      } 
     } 

     // update reference to hash table entry 
     lpf.first = true; 
     lpf.second = index; 
    } 
    return best_distance; 
} 

Answer 2

各要素をインデックスのセットにマップできます。だから、map<int, set<int>> mのようなものがあり、ベクトル：for(int i = 0, i < nums.size(); ++i) m[nums[i]].insert(i)を通過します。その後、マップを反復することができ、要素に複数のインデックスがある場合は、インデックス間の最小距離を見つけます。 O（nlog（n））でなければなりません。