LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用数组保存值，用哈希表保存值的索引

class RandomizedSet {
 public:
  /** Initialize your data structure here. */
  RandomizedSet() {}

  /** Inserts a value to the set. Returns true if the set did not already
   * contain the specified element. */
  bool insert(int val) {
    if (m.count(val)) {
      return false;
    }
    v.emplace_back(val);
    m.emplace(val, size(v) - 1);
    return true;
  }

  /** Removes a value from the set. Returns true if the set contained the
   * specified element. */
  bool remove(int val) {
    if (!m.count(val)) {
      return false;
    }
    v[m[val]] = v.back();
    m[v.back()] = m[val];
    v.pop_back();
    m.erase(val);
    return true;
  }

  /** Get a random element from the set. */
  int getRandom() { return v[rand() % size(v)]; }

 private:
  unordered_map<int, int> m;
  vector<int> v;
};