随机数索引

问题描述

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

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

示例:
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;
    }
};

链表随机节点

问题描述

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:
// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

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

思路

• 首先，将链表存到一个一维数组中
• 然后，int n=tmp.size();return tmp[random()%n]即可

题解

class Solution {
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    vector<int> tmp;
    Solution(ListNode *head) {
        ListNode *p=head;
        while (p){
            tmp.push_back(p->val);
            p=p->next;
        }
    }

    /** Returns a random node's value. */
    int getRandom() {
        int n=tmp.size();
        return tmp[random()%n];
    }
};

有序矩阵中第K小的元素

问题描述

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。

示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。

说明:
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix

思路

• 将矩阵存到一个一维数组中
• 对数组进行排序
• return下标为k-1的元素即可。

题解

class Solution {
public:
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        int n = matrix.size();
        int ret;
        vector<int> tmp;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tmp.push_back(matrix[i][j]);
            }
        }
        sort(tmp.begin(),tmp.end());
        return tmp[k-1];
    }
};

只出现一次的数字 III

问题描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

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

注意：
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-iii

思路

• 首先将数组进行排序

• 遍历一次数组

  首尾两个元素进行特判,看头元素是否不等于第二个元素，看尾元素是否不等于倒数第二个元素
  对于中间元素，看起是否不等于前一个元素，或者不等于后一个元素

题解

class Solution {
public:
    vector<int> singleNumber(vector<int> &nums) {
        vector<int> B;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size() - 1; i++) {
            if (nums[i] != nums[i + 1] && nums[i] != nums[i - 1]) {
                B.push_back(nums[i]);
            }
        }
        if (nums[0] != nums[1]) {
            B.push_back(nums[0]);
        }
        if (nums[nums.size() - 2] != nums[nums.size()-1])
        {
            B.push_back(nums[nums.size()-1]);
        }
        return B;
    }
};