398. 随机数索引-哈希表法
2023-09-14 09:06:52 时间
398. 随机数索引
给你一个可能含有 重复元素 的整数数组 nums ,请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。
实现 Solution 类:
Solution(int[] nums) 用数组 nums 初始化对象。
int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引,则每个索引的返回概率应当相等。
示例:
输入
[“Solution”, “pick”, “pick”, “pick”]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
输出
[null, 4, 0, 2]
解释
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
solution.pick(1); // 返回 0 。因为只有 nums[0] 等于 1 。
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
解题代码如下:
typedef struct {
long long index;
long long val;
struct Solution *next;
} Solution;
Solution* solutionCreate(int* nums, int numsSize) {
Solution *l=(Solution *)malloc(sizeof(Solution)*10000);
int i;
for(i=0;i<10000;i++){
(l+i)->next=NULL;
}
for(i=0;i<numsSize;i++){
Solution *p=(Solution *)malloc(sizeof(Solution));
p->index=i;
p->val=nums[i];
p->next=(l+abs(nums[i])%10000)->next;
(l+abs(nums[i])%10000)->next=p;
}
return l;
}
int solutionPick(Solution* obj, int target) {
Solution * p=(obj+abs(target)%10000)->next;
int count=0;
int pc=rand();
while(p){
if(p->val==target){
count++;
}
p=p->next;
}
pc=pc%count;
int cz=0;
p=(obj+abs(target)%10000)->next;
while(p){
if(p->val==target){
if(cz==pc){
return p->index;
}
cz++;
}
p=p->next;
}
return -1;
}
void solutionFree(Solution* obj) {
}
/**
* Your Solution struct will be instantiated and called as such:
* Solution* obj = solutionCreate(nums, numsSize);
* int param_1 = solutionPick(obj, target);
* solutionFree(obj);
*/
相关文章
- 【说站】mysql中哈希索引的使用限制
- MySQL实战之深入浅出索引(下)
- SQLServer 错误 2512 表错误:对象 ID O_ID,索引 ID I_ID,分区 ID PN_ID,分配单元 ID A_ID (类型为 TYPE)。 页 P_ID1 槽 SLOT1 和页 P_ID2 槽 SLOT2 中的重复键。 故障 处理 修复 支持远程
- 表簇 索引化表簇 哈希簇详解程序员
- 如何使用 MySQL 建立索引(mysql怎么建索引)
- Oracle中删除索引的方法(oracle如何删除索引)
- Oracle 索引分区:实现优化查询(oracle索引分区)
- 如何优化Oracle数据库中的多索引结构(oracle多个索引吗)
- Oracle索引结构解析详解(索引结构oracle)
- MySQL索引过长的解决方法:缩短索引长度,使用前缀索引或哈希索引。(mysql索引太长)
- Oracle中的哈希索引:让查询效率飞快(哈希索引 oracle)
- MSSQL索引实现多值配置(mssql非唯一索引)
- Oracle数据库重建主键索引的技巧(oracle重建主键索引)
- 索引Oracle将一条索引拆分为多条索引的方法(oracle一条拆分多条)
- oracle索引不能使用深入解析
- Oracle与Mysql主键、索引及分页的区别小结