Leetcode 398 随机数索引
2022/4/26 6:16:40
本文主要是介绍Leetcode 398 随机数索引,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Given an integer array nums
with possible duplicates, randomly output the index of a given target
number. You can assume that the given target number must exist in the array.
Implement the Solution class:
Solution(int[] nums)
Initializes the object with the arraynums
.int pick(int target)
Picks a random indexi
fromnums
wherenums[i] == target
. If there are multiple valid i's, then each index should have an equal probability of returning.
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/random-pick-index
实现方法比较垃圾,差不多是离散化之后记录下每个数字出现的位置,然后记录有几个位置,然后循环输出(竟然真的会检测概率相等)。
class Solution { public: map<int, int> m; vector<int> t, now; vector<vector<int>> g; Solution(vector<int>& nums) { vector<int> cop = nums; std::sort(nums.begin(), nums.end()); int N = nums.size(), cnt = 0; m.insert(make_pair(nums[0], cnt++)); nums[0] = m[nums[0]], g.push_back(vector<int>()), t.push_back(0), now.push_back(0); for (int i = 1; i < N; i++) { if (nums[i] != nums[i-1]) m.insert(make_pair(nums[i], cnt++)), g.push_back(vector<int>()), t.push_back(0), now.push_back(0); nums[i] = m[nums[i]]; } for (int i = 0; i < N; i++) { g[m[cop[i]]].push_back(i); t[m[cop[i]]]++; } } int pick(int target) { if (m.find(target) == m.end()) return -1; else { int tem = m[target]; now[tem] = (now[tem] + 1) % t[tem]; return g[tem][now[tem]]; } } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(nums); * int param_1 = obj->pick(target); */
这篇关于Leetcode 398 随机数索引的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验