随机数索引

问题描述

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);

// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/random-pick-index

思路

基本思路就是用map实现。

• 首先，遍历数组，得到元素和元素索引的映射
• 然后，得到和target对应的索引
• 最后，随机返回一个索引即可。

题解

class Solution {
public:
    map<int,vector<int>> table;
    Solution(vector<int>& nums) {
       for(int i=0;i<nums.size();i++){
           table[nums[i]].push_back(i);
       }
    }
    int pick(int target) {
        vector<int> tmp;
        tmp=table[target];
        int n=tmp.size();
        return tmp[random()%n];
    }
};

根据字符出现频率排序

问题描述

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:
输入:
"tree"
输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:
输入:
"cccaaa"
输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:
输入:
"Aabb"
输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。

注意'A'和'a'被认为是两种不同的字符。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-characters-by-frequency

思路

• 基本思路是用map来实现。
• 首先，对字符串s为空时，进行特判。
• 然后，字符串s不为空时，遍历s，将字符和其出现次数之间形成k-v映射。按照出现次数对映射进行排序。
  按照排序后的映射，生成返回结果字符串ret。

题解

class Solution {
public:
    static bool cmp(pair<char,int> tmp1,pair<char,int> tmp2){
        return tmp1.second>tmp2.second;
    }
    string frequencySort(string s) {
        int n = s.size();
        string ret;
        if (n == 0) return ret;
        map<char,int> table;
        for(int i=0;i<n;i++){
            table[s[i]]++;
        }
        vector<pair<char,int>> tmp;
        for(auto each:table){
            tmp.push_back(each);
        }
        sort(tmp.begin(),tmp.end(),cmp);
        for(auto each: tmp){
            for(int i=0;i<each.second;i++){
                ret+=each.first;
            }
        }
        return ret;
    }
};

字母异位词分组

问题描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

说明：
所有输入均为小写字母。
不考虑答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams

思路

使用map映射

• 如果单词是异位词，那么他们本身对sort排序后，应该相同的。
• 所以，异位词会在同一个k的映射下（不知道这种表述对不对，大概是这个意思...）
  map<string, vector<string>> table
  比如，eat排序后为aet，tea排序后也为aet，所以，aet对应eat，aet也对应tea。

• 将结果存到vector<vector<string>> ret即可。

  题解

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        vector<vector<string>> ret;
        map<string, vector<string>> table;
        for (const string &str : strs) {
            string buf = str;
            sort(buf.begin(), buf.end());
            table[buf].push_back(str);
        }
        for (const auto &each : table) {
            ret.push_back(each.second);
        }
        return ret;
    }
};

前 K 个高频元素

问题描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

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

示例 2:
输入: nums = [1], k = 1
输出: [1]

说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements

思路

首先，在元素与元素出现次数之间建立一个map映射；
然后申请一个pair<int,int>类型的vector，并将这些映射关系存入到vector中。
将vector中元素按照second（元素出现次数）从大到小排序。
最后，将前k个pair元素的first（元素值）存入到一个vector即可。

题解

class Solution {
public:
    static bool cmp(const std::pair<int, int> &left, const std::pair<int, int> &right) {
        return left.second > right.second;
    }
    vector<int> topKFrequent(vector<int> &nums, int k) {
        std::map<int, int> count;
        for(int i=0;i<nums.size();i++) count[nums[i]]++;
        vector<pair<int, int>> buf;
        for(auto each:count) buf.push_back(each);
        sort(buf.begin(), buf.end(), cmp);
        vector<int> ans;
        for (auto each:buf) {
            if (ans.size() < k) {
                ans.push_back(each.first);
            }
        }
        return ans;
    }
};

小菜鸡对map的理解

map是key-value的对应关系。

平时用的话,假如k-v都是int型，那么map<int,int> tmp即可。
map是自动有序的，是根据key递增的顺序进行排序的。

内部实现的简单化理解

可以把map想象成两部分：
第一部分-pair<int,int> buf这一部分是key-value;
第二部分-搜索二叉树，节点为pair类型。

假设现在有<3,4>,<4,10>,<7,6>,<6,4>,<4,2>
最开始搜索树是空的，建立根节点<3,4>；
下一个<4,10>的key=4>3,所以<4,10>为根节点<3,4>的右子树；
同理，<7,6>为<4,10>的右子树；
而6<7,所以<6,4>为<7,6>的左子树。
4出现在<4,10>的节点上，所以用2替换10;