algorithm - 如何找到整数数组中的最大非重复数？

Question

假设我有一个未排序的整数数组 {3, -1, 4, 5, -3, 2, 5}，我想找到最大的非重复数(在本例中为 4)(5 无效，因为它是重复的)。我怎样才能做到这一点？

Answer 1

使用无序映射来计算每个元素的频率。 (作为优化，跟踪遇到的最大元素并跳过低于该元素的元素。)然后，扫描 map 以找出频率恰好等于 1 的最大元素。

template <typename T>  // numeric T
pair<T, bool> FindMaxNonRepeating(vector<T> const& vec) {
  unordered_map<T, int> elem2freq;
  for (auto const& elem : vec) {
    elem2freq[elem] += 1;
  }

  T largest_non_repetitive = std::numeric_limits<T>::min();
  bool found = false;
  for (auto const& item : elem2freq) {
    if (item.first > largest_non_repetitive && item.second == 1) {
      largest_non_repetitive = item.first;
      found = true;
    }
  }

  return {largest_non_repetitive, found};
}

时间复杂度为 O(n)，空间复杂度为 O(n)。