从数组中删除唯一元素的最有效方法

Question

在C++中消除数组中唯一元素的有效方法是什么？

阵列式给出：

9, 8, 4, 9, 21, 3, 1, 4, 6, 2, 5, 6, 7, 12, 3, 6, 9, 1, 3 // keep duplicates, delete uniques 

输出：

9, 4, 9, 3, 1, 4, 6, 6, 3, 6, 9, 1, 3 // all duplicates 

Answer 1

void rmdup(int *array, int length) 
{ 
    int *current , *end = array + length - 1; 

    for (current = array + 1; array < end; array++, current = array + 1) 
    { 
     while (current <= end) 
     { 
      if (*current == *array) 
      { 
       *current = *end--; 
      } 
      else 
      { 
       current++; 
      } 
     } 
    } 
} 

//希望这有助于ü

Answer 2

我会使用C++套，其对数的复杂性（编辑： Scheff说）。

该解决方案具有为O（n log n）的算法的复杂性：

#include <set> 
#include <iostream> 

int main(int argc, char** argv) { 
    int nums[] = {9, 8, 4, 9, 21, 3, 1, 4, 6, 2, 5, 6, 7, 12, 3, 6, 9, 1, 3}; 
    std::set<int> s; 
    std::set<int> dups; 

    for (int i = 0; i < 19; ++i) 
     if (!s.insert(nums[i]).second) 
      dups.insert(nums[i]); 

    for (int i = 0; i < 19; ++i) 
     if (dups.find(nums[i]) != dups.end()) 
      std::cout << " " << nums[i]; 
    std::cout << std::endl; 

    return 0; 
} 

Answer 3

我可能会做这样的：

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

int main(int argc, char* argv[]) { 
    std::vector<int> nums = {9, 8, 4, 9, 21, 3, 1, 4, 6, 2, 
          5, 6, 7, 12, 3, 6, 9, 1, 3}; 
    // build histogram 
    std::map<int, int> counts; 
    for (int i : nums) ++counts[i]; 
    // copy elements that appear more than once 
    std::vector<int> result; 
    std::copy_if(nums.begin(), nums.end(), 
       std::back_inserter(result), 
       [&](int x){ return counts[x] > 1; }); 
    // print result 
    for (int i : result) { 
     std::cout << i << " "; 
    } 
    std::cout << "\n"; 
} 

输出是：

$ g++ test.cc -std=c++11 && ./a.out 
9 4 9 3 1 4 6 6 3 6 9 1 3 

这是两回合，你建立一个BST。如果您觉得速度太慢，您可以尝试使用std::unordered_map构建直方图，该插件在插入和查找方面具有更好的复杂性特征。

如果您想从原始矢量中删除重复项而不是构建另一个重复项，则可以使用erase-remove idiom。 （这是作为练习给读者的。）

Answer 4

这是怎么回事？

#include <set> 
#include <vector> 
#include <iostream> 
#include <algorithm> 

using namespace std; 

int main(int argc, char** argv) { 
    vector<int> nums = {9, 8, 4, 9, 21, 3, 1, 4, 6, 2, 5, 6, 7, 12, 3, 6, 9, 1, 3}; 
    std::set<int> s; 
    vector<int> dups; 

    for(auto i:nums) 
     if (!s.insert(i).second) 
      dups.push_back(i); 

    for_each(dups.begin(),dups.end(),[](int a){cout<<a<<" ";}); 
    cout << endl; 

    return 0; 
} 

只有一个通过。