如何在整数数组中找到最大非重复数? [英] How do a find the maximum non-repeating number in an integer array?

问题描述

假设我有一个未排序的整数数组{3，-1，4，5，-3，2，5}，并且我想找到最大非重复数(在这种情况下为4)(5无效，因为重复).我该如何实现?

Suppose I have an unsorted integer array {3, -1, 4, 5, -3, 2, 5}, and I want to find the maximum non-repeating number (4 in this case) (5 being invalid as it is repeated). How can I achieve this?

推荐答案

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

Use an unordered map to count the frequencies of each element. (As an optimization, keep track of largest element encountered and skip elements lower than that.) Then, scan the map to find out the largest element with frequency exactly equal to 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).

This runs in time complexity O(n) and requires space complexity O(n).

这篇关于如何在整数数组中找到最大非重复数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！