並べ替えられた配列から重複を削除

Question

QUS：並べ替えられた配列から重複を削除します。ソートされた配列が与えられた場合、各要素が1回だけ表示され、新しい長さが返されるようにします。私たちが望むにもかかわらず、あなたは別の配列のための余分なスペースを割り当てないでください

場所でだけでなく、元の配列を変更することを確認し、新しい長さを返すために

注意、あなたは一定のメモリを搭載した場所でこれを行う必要があります。

私は次のコードを試しましたが、誰かが私が間違っているのを助けることができますか？

#include<iostream> 
    #include<vector> 
    using namespace std; 

    int removeDuplicates(vector<int> &A) { 
     int m=A.size(); 
     if(m<=1) return m; 
     vector<int> :: iterator i=A.begin(); 
     vector<int> :: iterator j=A.begin()+1; 
     vector<int> :: iterator temp; 
     while(i!=A.end() && j!=A.end()) 
     { 
      while(j!=A.end() && *i == *j) 
      { 
       temp=j; 
       j++; 
       A.erase(temp); 
      } 
      i=j; 
      j++; 
     } 
     return A.size(); 
    } 

    int main() 
    { 
     vector<int> vec={0,0,0,0,0,0,0,4,4,7,7,7,7,9}; 
     cout<<"ans="<<removeDuplicates(vec); 
     return 0; 
    } 

Answer 1

あなたはそれがこのようにイテレータを使用して行うことができます。

#include<iostream> 
#include<vector> 

using namespace std; 

int removeDuplicates(vector<int> &A) { 
    int m = A.size(); 
    if(m <= 1) return m; 

    for (auto it1 = A.begin(); it1 != A.end(); it1++) { 
     for (auto it2 = it1 + 1; it2 != A.end();) { 
      if (*it1 == *it2) { 
       it2 = A.erase(it2); 
      } else { 
       it2++; 
      } 
     } 
    } 

    return A.size(); 
} 

int main() 
{ 
    vector<int> vec = { 0, 0, 0, 0, 0, 0, 0, 4, 4, 7, 7, 7, 7, 9 }; 
    cout << "ans=" << removeDuplicates(vec); 
    return 0; 
} 

Answer 2

あなたがjをインクリメントすると、その後、eraseそこ要素、J + 1から始まる要素が下に移動されています。インクリメントして要素をスキップしています。

より良いアプローチは、反復しない要素をある反復子から他の反復子に単純にコピーし、メインループの最後に新しい長さを設定することです。あなたの現在のアプローチは潜在的にO（n^2）であり、実用には遅すぎます。

Answer 3

アレイを使用するように求められます。ベクターは多くの点で似ていますが、同じではありません。以下のサンプルコードを見てください。

さらに、割り当てられたメモリを同じにしておくように求められます。ベクトルを使用すると、要素を追加/削除した後にサイズが拡大/縮小され、要素が削除されるとベクトルの後ろの配列のデータが再割り当てされ、書き換えられることは保証できません。

int main() 
{ 

    int arr[14] = {0,0,0,0,0,4,4,4,4,5,5,5,7,9}; 
    int last_non_duplicate_index = 0; 
    int current_index = 0; 
    int size = 14; 
    int new_size = size; 
    bool is_last_value = false; 

    // you can use for interchangeably 
    while(!is_last_value) 
    { 
     current_index++; // move one position ahead 
     if(current_index < size) // out of bonds check 
     { 
      if(arr[last_non_duplicate_index] != arr[current_index]) // value at position of current index is different 
      { 
       last_non_duplicate_index++; // increase index of the last value which was not a duplicate by one 
       arr[last_non_duplicate_index] = arr[current_index]; // write at that index 
       // e.g. if last index was 0 -> increase it to 1 and rewrite whatsever under arr[1] (current index) 
      } 
      else // values are the same 
      { 
       new_size--; // devrease the size 
      } 
     } 
     else 
     { 
      is_last_value = true; // current_index >= size -> out of bonds 
     } 
    } 

    for (int i = 0; i < new_size; i++) 
    { 
     std::cout << "arr[" << i << "]" << " = " << arr[i] << std::endl; 
    } 
    std::cout << "New size: " << new_size << std::endl; 
    return 0; 
} 

Answer 4

私はこれが必要だと思います。この関数は配列をテールからヘッドにループし、同じ値を数えます。その後、ユニークでない値に対して既にユニークな値のシフトを実行します。 ベクトル内部でメモリを再割り当てする必要があるため、ベクトル処理の実際のサイズは変更されません。

int removeDuplicates(vector<int> &vec) { 
    int currentVal = vec.size() - 1; 
    int uniqueNumber = 0; 

    while (currentVal >= 0) { 
     ++uniqueNumber; 
     int sameVal = currentVal; 
     while (sameVal > 0 && vec[sameVal - 1] == vec[currentVal]) 
      --sameVal; 

     int shiftSize = uniqueNumber; 
     for (int k = 1; k < shiftSize; ++k) { 
      vec[sameVal + k] = vec[currentVal + k]; 
     } 

     currentVal = sameVal - 1; 
    } 
    return uniqueNumber; 
}