分类 小菜鸡对map的理解 下的文章

求众数 II

问题描述

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1：
输入: [3,2,3]
输出: [3]

示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii

思路

  • 基本思路是用map（之前介绍过map内部实质是pair类型的）。
  • 对于map中的每一项，只要它的second值大于n/3，就将其存入返回结果ret中。

题解

class Solution {
public:
    vector<int> majorityElement(vector<int> &nums) {
        map<int, int> table;
        vector<int> ret;
        int n = nums.size();
        if (n == 0) return ret;
        for (int i = 0; i < n; i++) {
            table[nums[i]]++;
        }
        for(auto each:table){
            if(each.second>n/3) ret.push_back(each.first);
        }
        return ret;
    }
};

常数时间插入、删除和获取随机元素

问题描述

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
// 2 已在集合中，所以返回 false 。
randomSet.insert(2);
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1

思路

基本思路是用map来实现，map<int,int> table;

  • 插入
    插入val前先查看table[val]是否等于0；
    如果等于0，则table[val]++,表示集合中插入了val，并return true；
    否则return false；
  • 删除
    删除val前先查看table[val]是否等于1；
    如果等于1，则table[val]--,表示从集合中删除val，并return true；
    否则return false；
  • 随机返回

将集合中元素存到一个数组中，然后 int n=tmp.size();return tmp[random()%n]即可。

题解

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    map<int,int> table;
    RandomizedSet() {
        
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(table[val]>=1){
            return false;
        } 
        table[val]++;
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(table[val]==1){ 
            table[val]--;
            return true;
        }
        return false;
    }

    /** Get a random element from the set. */
    int getRandom() {
        vector<int> tmp;
        for(auto each:table){
            if(each.second==1){
                tmp.push_back(each.first);
            }
        }
        int n=tmp.size();
        return tmp[random()%n];
    }
};
  1. 1
  2. 2