알고리즘/LeetCode

LeetCode 풀기 - 382. Linked List Random Node

앤테바 2022. 1. 11. 06:24
반응형

382. Linked List Random Node

https://leetcode.com/problems/linked-list-random-node/

 

Linked List Random Node - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

문제)

솔루션1) 리스트를 배열로 저장

시간복잡도 : O(1)

공간복잡도 : O(n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.nodes = []
        
        cur = head
        while cur:
            self.nodes.append(cur.val)
            cur = cur.next
            
    def getRandom(self) -> int:
        return random.choice(self.nodes)

솔루션2) Reservior sampling

시간 복잡도 : O(n)

공간 복잡도 : O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.head = head
        
    # reservior sampling
    def getRandom(self) -> int:
        res = 0        
        cur = self.head
        i = 0
        
        while cur:
            if random.randint(0, i) == 0:
                res = cur.val
            
            cur = cur.next
            i += 1
        return res

솔루션3) 리스트 길이를 사전에 체크

시간 복잡도 : O(n)

공간 복잡도 : O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.n = 0
        self.head = head
        cur = head
        
        while cur:
            self.n += 1
            cur = cur.next
        
    def getRandom(self) -> int:
        n = random.randint(0, self.n - 1)
        cur = self.head
        while n > 0:
            cur = cur.next
            n -= 1
        return cur.val

 

반응형