数据结构可以构造如下：

• 将所有具有相同计数的键存储在HashSet keys中，并将其与count的值一起设置：让我们将这对count和{{ 1}}“桶”。

• 对于每个至少有一个键的计数值，您将拥有一个存储桶。将存储桶放入双向链接列表keys中，并按计数对其进行排序。

• 还创建一个HashMap bucketList，将密钥映射到当前存储该密钥的存储桶（该密钥列在存储桶的bucketsByKey集中）

然后keys操作很简单：从FindMinKey获取第一个存储桶，从bucketList集（无论哪个）中获取一个密钥，然后将其返回。与keys类似。

FindMaxKey操作将执行以下步骤：

1. 从Inc(key)获取与key对应的存储桶
2. 如果该存储桶存在，请从其bucketsByKey集中删除密钥。
3. 如果该集恰好变空，请从keys移除存储桶
4. 如果bucketList中的下一个存储桶的计数为1，则将密钥添加到它的集合中，并更新bucketList，以便它为此密钥引用该存储桶。
5. 如果bucketsByKey中的下一个存储桶具有不同的计数（或者没有更多的存储桶），则使用正确的计数和键创建一个新存储桶，并将其插入到{{1 }} –或如果找不到下一个存储桶，只需在末尾添加新的存储桶即可。
6. 如果在步骤2中没有找到该密钥的存储桶，则假定其计数为0，并从bucketList中获取第一个存储桶，并将其用作从第4步开始的“下一个存储桶”。
li>

bucketList的处理过程类似，除了发现计数已经为1时，什么也没有发生。

这是JavaScript中的交互式代码段，您可以在此处运行。它对HashMap使用本机bucketList，对HashSet使用本机Dec(key)，并实现一个双向链接列表作为循环列表，其中开始/结束由“前哨”节点标记（不包含）。数据）。

您可以按Inc / Dec按钮以选择所需的键，并监视Map和Set的输出以及对数据结构的简单查看。

FindMinKey

FindMaxKey

这是我的答案，但我仍然不确定我是否没有违反面试官所想到的任何情况。

我们将保留一个LinkedList，其中每个元素都有其对应的键和值，以及指向其上一个和下一个元素的指针，并始终按值排序。我们将每个键的指针存储在LinkedList中。此外，对于我们看到的每个新数字，我们添加两个元素以查看每个数字的开始和结束元素，并将存储指向它们的指针。由于我们每次操作最多要添加两个额外的元素，因此仍然是O（1）。

现在对于每个操作（例如增量），我们可以使用字典找到对应于此键的元素在LinkedList中的位置（假设字典以O（1）的时间复杂度工作），现在我们找到最后一个元素在具有相同值的LinkedList中（我们可以使用与该值的末尾相对应的元素来完成此操作，并向后移一个元素）并交换这两个指针（这只是一次简单的交换，并且此交换不会影响其他元素）接下来，我们将该元素与下一个元素交换两次，以使它属于下一个数字的段（我们可能也需要添加该数字），需要跟踪的最后一件事是最小值和最大值如果要更改的元素是当前的最小值或最大值，并且没有相同值的数字（LinkedList中该值的开始和结束元素是连续的），则必须更新该值

不过，我认为这种方法可以改进。

关键是问题只要求dec（1）或inc（1）。因此，该算法仅需要向前或向后移动一个块。这是一个很重要的先决条件，并且可以提供很多信息。

我测试过的代码：

template <typename K,uint32_t N>
struct DumbStructure {
 private:
  const int head_ = 0,tail_ = N - 1;

  std::unordered_map<K,int> dic_;

  int l_[N],r_[N],min_ = -1,max_ = -1;
  std::unordered_set<K> keys_[N];

  void NewKey(const K &key) {
    if (min_ < 0) {
      // nothing on the list
      l_[1] = head_;
      r_[1] = tail_;
      r_[head_] = 1;
      l_[tail_] = 1;

      min_ = max_ = 1;
    } else if (min_ == 1) {
    } else {
      // min_ > 1
      l_[1] = head_;
      r_[1] = min_;
      r_[head_] = 1;
      l_[min_] = 1;

      min_ = 1;
    }
    keys_[1].insert(key);
  }

  void MoveKey(const K &key,int from_value,int to_value) {
    int prev_from_value = l_[from_value];
    int succ_from_value = r_[from_value];

    if (keys_[from_value].size() >= 2) {
    } else {
      r_[prev_from_value] = succ_from_value;
      l_[succ_from_value] = prev_from_value;

      if (min_ == from_value) min_ = succ_from_value;
      if (max_ == from_value) max_ = prev_from_value;
    }
    keys_[from_value].erase(key);

    if (keys_[to_value].size() >= 1) {
    } else {
      if (to_value > from_value) {
        // move forward
        l_[to_value] =
            keys_[from_value].size() > 0 ? from_value : prev_from_value;
        r_[to_value] = succ_from_value;
        r_[l_[to_value]] = to_value;
        l_[r_[to_value]] = to_value;
      } else {
        // move backward
        l_[to_value] = prev_from_value;
        r_[to_value] =
            keys_[from_value].size() > 0 ? from_value : succ_from_value;
        r_[l_[to_value]] = to_value;
        l_[r_[to_value]] = to_value;
      }
    }
    keys_[to_value].insert(key);

    min_ = std::min(min_,to_value);
    max_ = std::max(max_,to_value);
  }

 public:
  DumbStructure() {
    l_[head_] = -1;
    r_[head_] = tail_;
    l_[tail_] = head_;
    r_[tail_] = -1;
  }

  void Inc(const K &key) {
    if (dic_.count(key) == 0) {
      dic_[key] = 1;
      NewKey(key);
    } else {
      MoveKey(key,dic_[key],dic_[key] + 1);
      dic_[key] += 1;
    }
  }

  void Dec(const K &key) {
    if (dic_.count(key) == 0 || dic_[key] == 1) {
      // invalid
      return;
    } else {
      MoveKey(key,dic_[key] - 1);
      dic_[key] -= 1;
    }
  }

  K GetMaxKey() const { return *keys_[max_].begin(); }

  K GetMinKey() const { return *keys_[min_].begin(); }
};