当前位置：首页 > article >正文

力扣382：链表随机结点

article 2024/10/24 19:37:23

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

实现 Solution 类：

Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例：

输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]

思想：统计链表的长度，创建和链表一样大小的数组。将链表中的数据保存到数组中，利用数组的随机存储的特点，随机生成一个结点，然后访问数据即可。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



typedef struct {
    int *data;
    int len;
    
} Solution;


Solution* solutionCreate(struct ListNode* head) {
    Solution *s = (Solution*)malloc(sizeof(Solution));
    s->len=0;
    struct ListNode *p=head;
    //统计链表的长度
    while(p!=NULL){
        p=p->next;
        s->len++;
    }
    //分配链表长度的数组空间
    s->data = (int*)malloc(sizeof(int)*s->len);
    p=head;
    //将链表的值存到数组中
    for(int i=0;i<s->len;i++){
        s->data[i]=p->val;
        p=p->next;
    }
    return s;
}

int solutionGetRandom(Solution* obj) {
    int num = rand()%obj->len;//创建[0,len)的随机数
    return obj->data[num];
}

void solutionFree(Solution* obj) {
    if(obj->data!=NULL){
        free(obj->data);
    }
    if(obj!=NULL){
        free(obj);
    }
}

/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = solutionCreate(head);
 * int param_1 = solutionGetRandom(obj);
 
 * solutionFree(obj);
*/

时间复杂度O（n）；空间复杂度O（n）

查看全文

http://www.kler.cn/news/363405.html