정렬 된 배열에서 중복 제거

Question

QUS : 정렬 된 배열에서 중복 제거 정렬 된 배열이 주어지면 각 요소가 한 번만 나타나고 새 길이가 반환되도록 자리에서 중복을 제거하십시오. 우리가 원하는 비록 다른 배열에 대해 별도의 공간을 할당하지 마십시오

장소에서뿐만 아니라 원래의 배열을 변경해야합니다, 새 길이를 반환하는

주, 당신은 상수 메모리와 장소에서이 작업을 수행해야합니다 .

다음 코드를 시도했지만 아무도 내가 잘못 가고있는 부분을 도울 수 있습니까 ??

#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; 
}