如何从向量中删除所有重复实例<int>

Question

我已经尝试解决一个“简单”的 leetcode 问题两个小时了，我需要删除出现不止一次的 int 的每个实例，然后将非重复项加在一起。我已经尝试了大约 10 种不同的方法，但我只能将它归结为每个 int 的一个副本。这是我写过的最好的解决方案，但给定输入 {1,2,2,3,4} 它会 return {1,2,3,4} 而预期输出是 {1,3, 4}

  sort(nums.begin(), nums.end()); //Sort numerically
  nums.erase(unique(nums.begin(), nums.end()), nums.end()); 
  return (accumulate(nums.begin(), nums.end(), 0));

Answer 1

您可以使用 std::unordered_map<int, bool>，其中第二个（模板）参数 (bool) 指定值是否重复。它看起来像这样，

#include <unordered_map>
...

std::unordered_map<int, bool> uniqueCheckMap;
for (auto i : nums)
{
    if (uniqueCheckMap.find(i) == uniqueCheckMap.end())
        uniqueCheckMap[i] = false;
    else
        uniqueCheckMap[i] = true;    // Set the second (value) as true if duplicate entry is found.
}

nums.clear();
int sum = 0;
for (auto i : uniqueCheckMap)
{
    if (!i.second)
    {
        nums.push_back(i.first);
        sum += i.first;
    }
}

Answer 2

NlogN 复杂度，您无需预先排序：

Godbolt

#include <set>
#include <vector>

int main()
{
    std::vector<int> nums = {1,2,2,3,5};

    std::multiset<int> m (nums.begin(), nums.end());

    std::size_t sum = 0;
    for (const auto& elem : m)
    {
      sum += m.count(elem) == 1 ? elem : 0;
    }
}

更新：可以使用 std::unordered_multiset，因为我们不需要订购。

Answer 3

有很多解决方法，您可以遍历数组并使用 map 或其他方法查看数字存在的次数，然后再次遍历地图并将只出现一次的数字添加到一个新数组。您可以使用一个集合和一个 map<bool,int>，每次添加一个新数字时，您都会检查它是否存在。

if(!map[number]){
set.insert(number);
map[number]=true;
}else{
set.erase(number);
}

Answer 4

如果 O(n²) 不是问题...

const auto sum=std::accumulate(cbegin(nums), cend(nums), 0,
  [&](const auto &accum, const auto &elem)
  {
    return accum+(std::count(cbegin(nums), cend(nums), elem)>1 ? 0 : elem);
  });

Answer 5

set_difference 在这里很有帮助。它以您描述的方式删除了事件。

        auto ints = vector{4, 3, 2, 2, 1};

        sort(begin(ints), end(ints));
        std::vector<int> unique_ints;
        unique_copy(begin(ints), end(ints), back_inserter(unique_ints));

        vector<int> doubles;
        set_difference( begin(ints), end(ints),
                        begin(unique_ints), end(unique_ints),
                        back_inserter(doubles)
                        );

        vector<int> only_once;
        set_difference( begin(unique_ints), end(unique_ints),
                        begin(doubles), end(doubles),
                        back_inserter(only_once));

        copy(begin(only_once), end(only_once), ostream_iterator<int>(cout, ", "));
        cout << "\n";

另外...它似乎可以解决问题。

$ g++ -std=c++17 u.cpp  && ./a.out 
1, 3, 4,

Answer 6

或者您可以在 'equal ranges' 上使用循环，仅累积单个元素长的元素：

        sort(begin(ints), end(ints));

        int acc = 0;
        auto range = equal_range(begin(ints), end(ints), ints.front());

        while(range.first != end(ints)) {
                cout << *range.first << "+ ";
                if (distance(range.first, range.second) == 1){
                        acc += *range.first;
                }
                range = equal_range(range.second, end(ints), *range.second);
        }
        cout << " = " << acc << "\n";

如何从向量中删除所有重复实例<int>

How to remove all instances of a duplicate from a vector<int>

c++

algorithm

vector

data-structures

stdvector